# Combinatorial Proof Question: Vandermonde convolution identity

I'm really iffy on combinatorial proofs in general and now that there is a sum, it's just confused me even more. Can someone try and walk me through this proof?

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

• $$(1+x)^{m+n}=(1+x)^m(1+x)^n$$ – Lucian Feb 11 '14 at 0:28

There are $m$ men and $n$ women, and you need to pick a team of $r$ people. The LHS counts how many ways to do this directly, the RHS breaks this down into $k$ men and $r-k$ women.
• Consider, say, $k=3$. Then ${m\choose 3}$ chooses three men, and ${n\choose r-3}$ chooses $r-3$ women. We multiply because those two choices are independent. – vadim123 Feb 10 '14 at 23:44
Since $\ds{{n \choose r - k} = 0\ \mbox{when}\ k > r}$, we'll have $\ds{{m + n \choose r} = \sum_{k=0}^{m}{m \choose k}{n \choose r - k}}$