Evaluate $\sum\limits_{k = 0}^n \binom{n}{n-k} \binom{m}{k}$. Give combinatorical arguments.

Question

Evaluate $\sum\limits_{k=0}^n \binom{n}{n-k} \binom{m}{k}$, $n \leq m$. So far, I have $\sum\limits_{k=0}^n \binom{n}{n-k} \binom{m}{k}=\sum\limits_{k=0}^n \binom{n}{k} \binom{m}{k}$ since $\binom{n}{n-k} = \binom{n}{k}$. I believe I need to use Vandermonde's Identity somewhere, but I'm not sure what to do from where I'm at.

Answer 1

Vandermonde's Identity:

$$\sum\limits_{k=0}^r \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$$

Your expression you wish to evaluate is exactly this where we replace $r$ by $n$.

---

An example of a combinatorial argument: Suppose you have $n$ men and $m$ women. We wish to make a team of $n$ people. We could count how many ways we could do this by just choosing $n$ people directly from the $n+m$ total people. Alternatively we could count this by breaking into cases based on the number of men selected in the group which yields the expression given.