Exercise 1630Combinatorics › Counting principlesOlympiadAdded 3 Nov 2026

Vandermonde's identity

#Vandermonde#double counting#binomial

Statement

Show that $\binom{m+n}{k}=\sum_{j=0}^{k}\binom{m}{j}\binom{n}{k-j}$ .

Hint

Double count $k$ -subsets of a union of disjoint $m$ -set and $n$ -set.

Show solutionHide solution

Setup. Let $A$ with $|A|=m$ and $B$ with $|B|=n$ , disjoint.

Count $k$ -subsets of $A\cup B$ . $\binom{m+n}{k}$ .

Count by intersecting with $A$ . If $j$ elements from $A$ and $k-j$ from $B$ , there are $\binom{m}{j}\binom{n}{k-j}$ ways. Sum over $j$ .

Conclusion. Vandermonde's identity.