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 the left-hand side of 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 the remaining $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.

Title	Vandermonde identity
Canonical name	VandermondeIdentity
Date of creation	2013-03-22 14:08:49
Last modified on	2013-03-22 14:08:49
Owner	mps (409)
Last modified by	mps (409)
Numerical id	8
Author	mps (409)
Entry type	Theorem
Classification	msc 05A19
Related topic	PascalsRule