Summation proof

09132023, 02:11 AM
Post: #1




Summation proof
(09112023 03:48 PM)Albert Chan Wrote: \(\displaystyle \binom{x+n}{k} = 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{n1}{k1} = \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{n1}{k1}}{n1} + \left(\frac{n1}{k1}\right) \left(\frac{\binom{n2}{k2}}{n2} + \left(\frac{n2}{k2}\right) (...) \right) \right) \\ &= \binom{n}{k} \left(\frac{1}{n} + \frac{1}{n1} + \frac{1}{n2}+\;...\;+ \frac{1}{n(k1)} \right) \\ &= \binom{n}{k}\;\sum_{j=n(k1)}^{n} \frac{1}{j} \end{align}\) 

09132023, 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 

09132023, 02:54 AM
(This post was last modified: 09132023 11:21 AM by Albert Chan.)
Post: #3




RE: Summation proof
(09112023 03:48 PM)Albert Chan Wrote: \(\displaystyle \binom{x+n}{k}' \bigg\rvert_{x=0} 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}{kj} = \sum_{j=1}^{k} (1)^{j+1}\; \left( \binom{n1}{kj} + \binom{n1}{kj1}\right) = \binom{n1}{k1}\) 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{x1}{k1} = \binom{n}{k}\) \(\displaystyle \frac{d}{dn} \binom{n}{k} = \sum_{j=1}^{k} \frac{(1)^{j+1}}{j}\; \binom{n}{kj} \) Divide LHS by \(\binom{n}{k}\), we have: \(\displaystyle \frac{d}{dn} \ln \binom{n}{k} = \frac{d}{dn} \left( \ln(n!)  \ln((nk)!)  \ln(k!) \right) = \Psi(n+1)  \Psi(nk+1) = \sum_{j=n(k1)}^{n} \frac{1}{j} \) QED 

09132023, 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}{n1} + \frac{1}{n2} \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. 

09132023, 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' (09132023 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. 

09132023, 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:
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? 

09132023, 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 

09132023, 07:12 PM
Post: #8




RE: Summation proof
(09132023 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 .. n1), 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. 

09132023, 08:15 PM
(This post was last modified: 09132023 08:16 PM by John Keith.)
Post: #9




RE: Summation proof
(09132023 06:49 PM)rprosperi Wrote: Can someone... anyone... please tie this in, somehow, to calculators?? 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. 

09132023, 08:35 PM
Post: #10




RE: Summation proof
Hello!
(09132023 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 

09132023, 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)^(MNN) @ D(N)=0 30 FOR J=1 TO N @ D(N+J)=J^M @ D(NJ)=S*D(N+J) @ NEXT J 40 IF S<0 THEN D(M)=(N+1)^M 50 FOR I=0 TO M1 @ FOR J=M TO I+1 STEP 1 @ D(J)=D(J)D(J1) @ 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/(N1J) @ S=S+1/J @ C(NJ)=K*S @ NEXT J 120 FOR J=N1 TO M @ C(J)=C(J1)*(N1J1)/(J+1) @ NEXT J 130 DISP "B=";DOT(C,D) >run M= 6 B= 2.38095210526E2 >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^M1) >for m = 2 to 30 step 2 @ m, fnb(m) @ next m 2 .166666666667 4 3.33333333333E2 6 2.38095238095E2 8 3.33333333333E2 10 7.57575757576E2 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 

09142023, 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 

« Next Oldest  Next Newest »

User(s) browsing this thread: