Vandermonde identity

Theorem 1 ([1] 24.1.1 formula A. II.).

For any $p$ and $q$ and any $k$ with $0\\leq k\\leq p+q$ ,

\\binom{p+q}{k}=\\sum_{i=0}^{k}\\binom{p}{i}\\binom{q}{k-i}.{}

(*)

Proof.

Let $P$ and $Q$ be disjoint sets with $|P|=p$ and $|Q|=q$ . Then theleft-hand sideof Equation (*) is equal to the number of subsets of $P\\cup Q$ of size $k$ .To build a subset of $P\\cup Q$ of size $k$ , we first decide how many elements, say $i$ with $0\\leq i\\leq k$ ,we will select from $P$ . We can then select those elements in $\\binom{p}{i}$ ways. Once we have done so, we must select theremaining $k-i$ elements from $Q$ , which we can do in $\\binom{q}{k-i}$ ways. Thus there are $\\binom{p}{i}\\binom{q}{k-i}$ ways to select a subset of $P\\cup Q$ of size $k$ subject to the restriction that exactly $i$ elements come from $P$ . Summing over all possible $i$ completes the proof.∎

References

1 Abramowitz, M., and I. A. Stegun, eds. Handbook of Mathematical Functions. National Bureau of Standards, Dover, New York, 1974.