Alternating sum of product of binomial coefficients

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
GBog
Posts: 114
Joined: Fri Jun 01, 2007 4:57 pm UTC

Alternating sum of product of binomial coefficients

Postby GBog » Mon Nov 17, 2008 2:44 pm UTC

In a numerics project, I've encountered the apparent identity
[math]\sum_{i=0}^k (-1)^i {2s-i \choose s-i} {k \choose i} = {2s-k \choose s}[/math]
where [imath](0 \leq k \leq s)[/imath].
possibly with the generalization
[math]\sum_{i=0}^k (-1)^i {n-i \choose m-i} {k \choose i} = {n-k \choose m}[/math]
Does anyone know if any of these are known identities, or failing that, a good reference to identities of this flavour?

There was a very comprehensive list of binomial identities online earlier, but it appears to have disappeared some time in January this year.

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: Alternating sum of product of binomial coefficients

Postby t0rajir0u » Mon Nov 17, 2008 10:13 pm UTC

The quintessential identity of this type is Vandermonde's identity. The general technique, failing a combinatorial proof, is to look at generating functions. Vandermonde's identity, for example, is a trivial consequence of the equality of generating functions (x + 1)^n (x + 1)^m = (x + 1)^{n+m}.

User avatar
GBog
Posts: 114
Joined: Fri Jun 01, 2007 4:57 pm UTC

Re: Alternating sum of product of binomial coefficients

Postby GBog » Tue Nov 18, 2008 1:26 pm UTC

Thanks. Using generalized binomial coefficients and Vandermonde's identity did the trick.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 11 guests