# 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 VandermondeIdentity 2013-03-22 14:08:49 2013-03-22 14:08:49 mps (409) mps (409) 8 mps (409) Theorem msc 05A19 PascalsRule