Prove by Double Counting Method $\sum\limits_{k = 0}^m \binom{m}{k}\binom{n}{r + k} = \binom{m + n}{m + r}$

Question

Show by combinatorial arguments that:

$$\sum_{k = 0}^m \binom{m}{k}\binom{n}{r + k} = \binom{m + n}{m + r}$$

Hello , I want to prove this argument by double counting method, i kinda have an idea of proving by comb args. but not by double counting... Can someone give any clues or ideas? thanks :)

Answer 1

This is essentially Vandermonde's identity. Consider $m$ men and $n$ women. In how many ways may we pick a committee of $m+r$ members?

On the one hand, this is just $\binom{m+n}{m+r}$.

On the other hand, if we pick $m-k$ men, then we need to pick $r+k$ women. Hence we have $$\sum_{k=0}^m\binom{m}{k}\binom{n}{r+k}=\sum_{k=0}^m\binom{m}{m-k}\binom{n}{r+k}=\binom{m+n}{m+r}.$$