Vandermonde Identity
Intermediate
Lecture Notes
Here is the Vandermonde Identity: $$\sum_{k=0}^{r}{m\choose k}{n\choose r-k}={m\choose 0}{n\choose r}+{m\choose 1}{n\choose r-1}+{m\choose 2}{n\choose r-2}+\cdots +{m\choose r}{n\choose 0}={m+n\choose r}$$
It is a good example of proving combinatorial identity by using two different approaches to count the same thing.
We will see more examples of using this method in the next lesson The Multi-Approach Method.
Examples
(Vandermonde's Identity) Show that $$\displaystyle\sum_{k=0}^r\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}$$(4274)
Comments
Vandermonde Identity can be generalized in the following way: $$\sum_{k_1 + k_2 + \cdots + k_p=m}{n_1\choose k_1}{n_2\choose k_2}\cdots{n_p\choose k_p}={n_1+n_2+\cdots+n_p\choose m}$$