Post Reply 
Summation proof
09-13-2023, 02:11 AM
Post: #1
Summation proof
(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 Smile
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}\)
Find all posts by this user
Quote this message in a reply
09-13-2023, 02:37 AM
Post: #2
RE: Summation proof
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.

--Bob Prosperi
Find all posts by this user
Quote this message in a reply
09-13-2023, 02:54 AM (This post was last modified: 09-13-2023 11:21 AM by Albert Chan.)
Post: #3
RE: Summation proof
(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
Find all posts by this user
Quote this message in a reply
09-13-2023, 03:20 AM
Post: #4
RE: Summation proof
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. Smile
Find all posts by this user
Quote this message in a reply
09-13-2023, 03:52 AM
Post: #5
RE: Summation proof
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. Smile

\(\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.
Find all posts by this user
Quote this message in a reply
09-13-2023, 01:44 PM
Post: #6
RE: Summation proof
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?
Find all posts by this user
Quote this message in a reply
09-13-2023, 06:49 PM
Post: #7
RE: Summation proof
Can someone... anyone... please tie this in, somehow, to calculators??

It's all very nice, maybe even useful, but does it really belong here?

--Bob Prosperi
Find all posts by this user
Quote this message in a reply
09-13-2023, 07:12 PM
Post: #8
RE: Summation proof
(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]

[Image: 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.
Find all posts by this user
Quote this message in a reply
09-13-2023, 08:15 PM (This post was last modified: 09-13-2023 08:16 PM by John Keith.)
Post: #9
RE: Summation proof
(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. Smile 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.
Find all posts by this user
Quote this message in a reply
09-13-2023, 08:35 PM
Post: #10
RE: Summation proof
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
Find all posts by this user
Quote this message in a reply
09-13-2023, 11:18 PM
Post: #11
RE: Summation proof
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
Find all posts by this user
Quote this message in a reply
09-14-2023, 11:53 AM
Post: #12
RE: Summation proof
Thank you for the program, and as a bonus for me, the 71b is my favorite machine, so good choice!!

--Bob Prosperi
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 2 Guest(s)