Summation proof

[Albert Chan]

(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}\)

[rprosperi]

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.

[Albert Chan]

(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

[Albert Chan]

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.

[Albert Chan]

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.

[John Keith]

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?

[rprosperi]

Can someone... anyone... please tie this in, somehow, to calculators??

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

[Albert Chan]

(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

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.

[John Keith]

(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.

[Maximilian Hohmann]

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

[Albert Chan]

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

[rprosperi]

Thank you for the program, and as a bonus for me, the 71b is my favorite machine, so good choice!!