+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: Not HP Calculators (/forum-7.html)
+--- Forum: Not remotely HP Calculators (/forum-9.html)
+--- Thread: Summation proof (/thread-20493.html)
Summation proof - Albert Chan - 09-13-2023 02:11 AM
(09-11-2023 03:48 PM)Albert Chan Wrote: \(\displaystyle \binom{x+n}{k} =
\left(\frac{x+n}{k}\right) \binom{x+n-1}{k-1}
\)
\(\displaystyle \binom{x+n}{k}' \bigg\rvert_{x=0} =
\left(\frac{1}{k}\right) \binom{n-1}{k-1} +
\left(\frac{n}{k}\right) \binom{x+n-1}{k-1}'\bigg\rvert_{x=0}
\)
I had managed to undo recursion, into iterative sums (written prove welcome!)
\(\displaystyle \binom{x+n}{k}' \bigg\rvert_{x=0}
\;=\; \sum_{j=1}^{k} \frac{(-1)^{j+1}}{j}\; \binom{n}{k-j}
\;=\; \binom{n}{k}\;\sum_{j=n-(k-1)}^{n} \frac{1}{j}
\)
I was typing the question to Math StackExchange, then I figured out the proof
It is a bit OT to Bernoulli's number, so I start a new thread, for those interested.
Proving RHS is easy, if we noticed \(\displaystyle \left(\frac{1}{k}\right) \binom{n-1}{k-1} = \left(\frac{1}{n}\right) \binom{n}{k}\)
Also, if k is negative, comb(n, k) = 0. This explained why summation has exactly k terms.
\(\begin{align}
\displaystyle \binom{x+n}{k}' \bigg\rvert_{x=0} &=
\frac{\binom{n}{k}}{n} +
\left(\frac{n}{k}\right) \left(
\frac{\binom{n-1}{k-1}}{n-1} + \left(\frac{n-1}{k-1}\right)
\left(\frac{\binom{n-2}{k-2}}{n-2} + \left(\frac{n-2}{k-2}\right) (...) \right)
\right) \\
&= \binom{n}{k} \left(\frac{1}{n} + \frac{1}{n-1} + \frac{1}{n-2}+\;...\;+
\frac{1}{n-(k-1)} \right) \\
&= \binom{n}{k}\;\sum_{j=n-(k-1)}^{n} \frac{1}{j}
\end{align}\)
RE: Summation proof - rprosperi - 09-13-2023 02:37 AM
This is possibly impressive, maybe even important? How the heck is one to tell????
MATH...MATH...MATH...MATH...<POOF>...Result... doesn't answer the above question without some explanation of what it's for, why it matters, who should care, etc.
Possibly, 5% of the audience here read this and gasped in excitement; but it's the other 95% I am wondering about...
Please Albert, consider adding some explanatory text in posts like this to help others understand what is going on, and to hopefully appreciate what you're trying to convey and your analytical skills in developing and presenting them here. I know creating a post like this takes some time and effort to create, so help folks be able to appreciate it.
RE: Summation proof - Albert Chan - 09-13-2023 02:54 AM
(09-11-2023 03:48 PM)Albert Chan Wrote: \(\displaystyle \binom{x+n}{k}' \bigg\rvert_{x=0}
\;=\; \sum_{j=1}^{k} \frac{(-1)^{j+1}}{j}\; \binom{n}{k-j}
\;=\; \binom{n}{k}\;\sum_{j=n-(k-1)}^{n} \frac{1}{j}
\)
Proving the middle part is tricky, we had to drop j denominator first.
Without denominator j, it is a telescoping sum, only first term remain. (last term = 0)
\(\displaystyle \sum_{j=1}^{k} (-1)^{j+1}\; \binom{n}{k-j}
= \sum_{j=1}^{k} (-1)^{j+1}\; \left( \binom{n-1}{k-j} + \binom{n-1}{k-j-1}\right)
= \binom{n-1}{k-1}\)
To add back j denominator, we use the same trick for getting Bernoulli's number!
Summation, then take the derivative:
\(\displaystyle \sum_{x=1}^{n} \binom{x-1}{k-1} = \binom{n}{k}\)
\(\displaystyle \frac{d}{dn} \binom{n}{k} = \sum_{j=1}^{k} \frac{(-1)^{j+1}}{j}\; \binom{n}{k-j} \)
Divide LHS by \(\binom{n}{k}\), we have:
\(\displaystyle \frac{d}{dn} \ln \binom{n}{k}
= \frac{d}{dn} \left( \ln(n!) - \ln((n-k)!) - \ln(k!) \right)
= \Psi(n+1) - \Psi(n-k+1)
= \sum_{j=n-(k-1)}^{n} \frac{1}{j} \) QED
RE: Summation proof - Albert Chan - 09-13-2023 03:20 AM
Hi, rprosperi
The math is an optimization trick used in code. (recursion to iterative sum)
Based on experiments, I was 99% sure it is correct. Prove get the final 1%.
I don't know how to explain beauty of math, but consider the proof, for k=3
\(\displaystyle
\binom{n}{3} \left(
\frac{1}{n} + \frac{1}{n-1} + \frac{1}{n-2}
\right) =
\frac{1}{1}\binom{n}{2} -
\frac{1}{2}\binom{n}{1} +
\frac{1}{3}\binom{n}{0}\)
Why is this even true?
Where is the harmonic series comes from?
Well, harmonic series comes from Psi, derivative of log gamma function.
Eureka! RHS must be \(\displaystyle \frac{d}{dn} \binom{n}{3}\) in disguise.
RE: Summation proof - Albert Chan - 09-13-2023 03:52 AM
Another way to do this, very simply, without knowing Psi, Gamma ...
Product rule: (u * v)' = u * v' + v * u'
(09-13-2023 03:20 AM)Albert Chan Wrote: Eureka! RHS must be \(\displaystyle \frac{d}{dn} \binom{n}{3}\) in disguise.
\(\displaystyle RHS = \frac{d}{dn} \frac{(n)(n\!-\!1)(n\!-\!2)}{3!}
= \frac{(n\!-\!1)(n\!-\!2) + n(n\!-\!2) + n(n\!-\!1)}{3!}
= \binom{n}{3} \left( \frac{1}{n} + \frac{1}{n\!-\!1} + \frac{1}{n\!-\!2}\right)
= LHS
\)
Harmonic series appears because product rule act on 1 factor at time.
RE: Summation proof - John Keith - 09-13-2023 01:44 PM
To clarify my (rather rusty) recollection, the LHS reads "the derivative of COMB(n, k) where x = 0"? Also, can you explain the connection to Bernoulli numbers?
Empirically, here is a table of your function for n from 0 to 7 and k from 0 to n.
Code:
{ Inf }
{ '3/2' 1 }
{ '5/6' 1 '3/2' }
{ '7/12' 1 '5/2' '11/6' }
{ '9/20' 1 '7/2' '13/3' '25/12' }
{ '11/30' 1 '9/2' '47/6' '77/12' '137/60' }
{ '13/42' 1 '11/2' '37/3' '57/4' '87/10' '49/20' }
{ '15/56' 1 '13/2' '107/6' '319/12' '459/20' '223/20' '363/140' }The first three columns are very simple; subsequent columns do not seem obvious to me. Also, neither the numerators nor denominators are in the OEIS. Is there a combinatorial meaning to these numbers?
RE: Summation proof - rprosperi - 09-13-2023 06:49 PM
Can someone... anyone... please tie this in, somehow, to calculators??
It's all very nice, maybe even useful, but does it really belong here?
RE: Summation proof - Albert Chan - 09-13-2023 07:12 PM
(09-13-2023 01:44 PM)John Keith Wrote: To clarify my (rather rusty) recollection, the LHS reads "the derivative of COMB(n, k) where x = 0"? Also, can you explain the connection to Bernoulli numbers?
It is d/dn of comb(n,k). No, not evaluate at n=0. We are proving an identity.
Connection to Bernoulli number is simply the method of using falling factorial form.
B(m) = d/dn Σ(x^m, x = 0 .. n-1), evaluated at n = 0
Proving this thread identity, we did the same thing (except n=0 part): Σ, then d/dn
Once we recognized d/dn comb(n,k) connection, the proof is easy.
We can actually look it up, from wiki for Binomial coefficient
![[Image: dcada7ddac94f7bbdc43cbf587b47c4cdb22e9fe]](https://wikimedia.org/api/rest_v1/media/math/render/svg/dcada7ddac94f7bbdc43cbf587b47c4cdb22e9fe)
![[Image: 7d7b0f3358f8ad2e88b17c027fecc058ddb75eb6]](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d7b0f3358f8ad2e88b17c027fecc058ddb75eb6)
Quote:The first three columns are very simple; subsequent columns do not seem obvious to me.
k = 1 .. n. First column (k=0) is not used. Diagonal are harmonic numbers.
I don't know if coefficients have combinatorial meaning.
RE: Summation proof - John Keith - 09-13-2023 08:15 PM
(09-13-2023 06:49 PM)rprosperi Wrote: Can someone... anyone... please tie this in, somehow, to calculators??
It's all very nice, maybe even useful, but does it really belong here?
Well, I did use the HP 50g (in the form of EMU48) to make the table.
More to the point, Albert and I have developed several fast and accurate programs for computing Bernoulli numbers on many HP calculators, including ones that are significantly faster than the HP 49/50's IBERNOULLI function.I see many threads on subjects that do not interest me. These threads do not bother me, I simply don't read them.
RE: Summation proof - Maximilian Hohmann - 09-13-2023 08:35 PM
Hello!
(09-13-2023 08:15 PM)John Keith Wrote: ... developed several fast and accurate programs ...
If it is all about programs, it should be put into the rather large „Software“ section, shouldn't it?
Personally I don't care. As far as I am concerned, this forum does not need to be divided into different sections at all. But as it is, this division exists and therefore should be respected. A mathematical proof by itself has no direct connection to HP calculators - I think we all agree on this.
Regards
Max
RE: Summation proof - Albert Chan - 09-13-2023 11:18 PM
Here is HP71B code, that the coefficients are used.
It did work, but code really not suitable with approximate numbers.
10 DESTROY ALL @ OPTION BASE 0 @ INPUT "M= ";M
20 DIM C(M),D(M) @ N=M DIV 2 @ S=(-1)^(M-N-N) @ D(N)=0
30 FOR J=1 TO N @ D(N+J)=J^M @ D(N-J)=S*D(N+J) @ NEXT J
40 IF S<0 THEN D(M)=(N+1)^M
50 FOR I=0 TO M-1 @ FOR J=M TO I+1 STEP -1 @ D(J)=D(J)-D(J-1) @ NEXT J @ NEXT I
100 K=1 @ S=0 @ N1=N+1 @ C(N)=1/N1
110 FOR J=N TO 1 STEP -1 @ K=K*J/(N1-J) @ S=S+1/J @ C(N-J)=K*S @ NEXT J
120 FOR J=N1 TO M @ C(J)=C(J-1)*(N1-J-1)/(J+1) @ NEXT J
130 DISP "B=";DOT(C,D)
>run
M= 6
B= 2.38095210526E-2
>1/res
42.0000048632
The simple and accurate solution is with zeta correction.
>5 DEF FNB(M)=(-1)^(M/2+1)*(IP(2*FACT(M)/(PI^M)*(1+3^(-M)))+.5)/(2^M-1)
>for m = 2 to 30 step 2 @ m, fnb(m) @ next m
2 .166666666667
4 -3.33333333333E-2
6 2.38095238095E-2
8 -3.33333333333E-2
10 7.57575757576E-2
12 -.253113553114
14 1.16666666667
16 -7.09215686275
18 54.9711779449
20 -529.124242424
22 6192.12318841
24 -86580.2531135
26 1425517.16667
28 -27298231.0678
30 601580873.9
>fnb(100)
-2.83822495705E78
RE: Summation proof - rprosperi - 09-14-2023 11:53 AM
Thank you for the program, and as a bonus for me, the 71b is my favorite machine, so good choice!!