Alternating sum of product of binomial coefficients

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

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

Alternating sum of product of binomial coefficients

In a numerics project, I've encountered the apparent identity
$\sum_{i=0}^k (-1)^i {2s-i \choose s-i} {k \choose i} = {2s-k \choose s}$
where [imath](0 \leq k \leq s)[/imath].
possibly with the generalization
$\sum_{i=0}^k (-1)^i {n-i \choose m-i} {k \choose i} = {n-k \choose m}$
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.

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

Re: Alternating sum of product of binomial coefficients

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

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

Re: Alternating sum of product of binomial coefficients

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