6
$\begingroup$

I stumbled across this identity involving binomial coefficients this morning:

If $n$, $k$, $a$, and $b$ are positive integers and $n=a+b$, then

$ \binom{n}{k} =\sum_{i=0}^k \binom{a}{k-i}\binom{b}{i}.$

The proof is trivial. (Partition a set $N$ of $n$ things into disjoint sets $A$ of $a$ things and $B$ of $b$ things. Now to pick $k$ items from $N$, either all $k$ are from $A$, or $k-1$ are from $A$ and $1$ is from $B$, or...)

Has this identity appeared before (I expect the answer to be "Yes!") and if so, does it have a name?

  • 1
    In other words: show that the coefficients of the product of two generating functions is the convolution of the coefficients of the two generating functions.2011-09-29

1 Answers 1

12

That's Vandermonde's identity.

  • 4
    Chu-Vandermonde, if we must be complete... ;)2011-09-29