Toolkit 17

Vandermonde's Identity

\binom{m}{0}\binom{n}{k}+\binom{m}{1}\binom{n}{k-1}+\binom{m}{2}\binom{n}{k-2}+\cdots+\binom{m}{k}\binom{n}{0}=\binom{m+n}{k}

Proof

Consider a group of $m$ girls and $n$ boys. We want to select $k$ people from the entire group.

The total number of ways to do this is

\binom{m+n}{k}.

We can also count the selections according to the number of girls chosen.

If we choose $j$ girls, then we must choose $k-j$ boys. The number of such selections is

\binom{m}{j}\binom{n}{k-j}.

Considering all possible values of $j$ , from $0$ to $k$ , gives

\binom{m}{0}\binom{n}{k}+\binom{m}{1}\binom{n}{k-1}+\cdots+\binom{m}{k}\binom{n}{0}.

Both expressions count the same set of selections. Therefore,

\binom{m}{0}\binom{n}{k}+\binom{m}{1}\binom{n}{k-1}+\cdots+\binom{m}{k}\binom{n}{0}=\binom{m+n}{k}. \quad\square