A combinatorial identity
in [Math]
|
Prev: " FINAL CONVICTION STATEMENT TO THE WORLD OF MATHEMATICS BY DISCOVERS OF INVERSE 19"
Next: ---------- ---------- Wieferich prime
From: Stephen J. Herschkorn on 8 Aug 2010 23:07 Is this identity well-known? For 0 <= i < k, sum(j=i..k, (-1)^j C(j, i) C(k, j)) = 0, where C(_, _) denotes the binomial coefficient. I needed it for something else I was working on. I've come up with a neat little proof if anyone is interested. -- Stephen J. Herschkorn sjherschko(a)netscape.net
From: Rob Johnson on 9 Aug 2010 01:05 In article <4C5F7109.6080401(a)netscape.net>, "Stephen J. Herschkorn" <sjherschko(a)netscape.net> wrote: >Is this identity well-known? For 0 <= i < k, sum(j=i..k, (-1)^j C(j, >i) C(k, j)) = 0, where C(_, _) denotes the binomial coefficient. I >needed it for something else I was working on. I've come up with a neat >little proof if anyone is interested. I believe it is well-known. At least I have used it before. The easiest proof I know uses negative binomial coefficients. To make the steps below valid, k >= i >= 0. k --- j > (-1) C(j,i) C(k,j) --- j=i k --- j = > (-1) C(j,j-i) C(k,k-j) --- j=i k --- i = > (-1) C(-i-1,j-i) C(k,k-j) --- j=i i = (-1) C(k-i-1,k-i) which is 0 for k > i, and (-1)^k for k = i. Rob Johnson <rob(a)trash.whim.org> take out the trash before replying to view any ASCII art, display article in a monospaced font
From: Stephen J. Herschkorn on 9 Aug 2010 01:54
Rob Johnson wrote: >In article <4C5F7109.6080401(a)netscape.net>, >"Stephen J. Herschkorn" <sjherschko(a)netscape.net> wrote: > > >>Is this identity well-known? For 0 <= i < k, sum(j=i..k, (-1)^j C(j, >>i) C(k, j)) = 0, where C(_, _) denotes the binomial coefficient. I >>needed it for something else I was working on. I've come up with a neat >>little proof if anyone is interested. >> >> > >I believe it is well-known. At least I have used it before. The >easiest proof I know uses negative binomial coefficients. To make >the steps below valid, k >= i >= 0. > > k > --- j > > (-1) C(j,i) C(k,j) > --- > j=i > > k > --- j > = > (-1) C(j,j-i) C(k,k-j) > --- > j=i > > k > --- i > = > (-1) C(-i-1,j-i) C(k,k-j) > --- > j=i > > i > = (-1) C(k-i-1,k-i) > >which is 0 for k > i, and (-1)^k for k = i. > > I am unfamiliar with negative binomial coefficients, so I have trouble following your last two steps; Here is my proof. sum(j=i..k, (-1)^j C(j, i) C(k, j)) = sum(j=i..k, (-1)^j k! / [i! (j-i)! (k-j!)]) = a sum(j=i..k, (-1)^j C(k-i, j-i)) (where a is a factor depending on i and k) = +/- a sum(j=0..k-i, (-1)^j C(k-i, j)) = +/- a (-1 + 1)^(k-i) = 0 for k > i. -- Stephen J. Herschkorn sjherschko(a)netscape.net |