Exercise 815Combinatorics › Binomial coefficientsL1Added 3 Nov 2026

Vandermonde's identity

#Vandermonde#convolution#binomial

Statement

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

Hint

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

Show solutionHide solution

Setup. $A$ with $|A|=m$ , $B$ with $|B|=n$ , $A\cap B=\emptyset$ .

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

Count by intersection with $A$ . Choose $k$ from $A$ and $r-k$ from $B$ : $\binom{m}{k}\binom{n}{r-k}$ . Sum over $k$ .

Conclusion. Vandermonde's identity.