Verify the following combinatorial identity: $\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$ $$\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$$
Nice, so I've proven some combinatorial identities before via induction, other more simple ones by committee selection models.... But this one is weird, induction doesn't even seem feasible here without things getting nasty, and the summation on the left is not making things easier. Can anyone help?

This is a classic double counting argument. We will count how many ways we can choose $r$ balls from $m+n$ balls.
If we place $m+n$ balls in a single urn, then the right hand side counts the number of ways we can select $r$ balls from the urn containing $m+n$ balls.
Suppose now we place $m$ balls in one urn and $n$ balls in the other. I can select a total of $r$ things from these two two urns by choosing $k$ balls from the first urn and $r-k$ balls from the second urn. Thus there are $\binom{m}{k}\binom{n}{r-k}$ ways for this selection to happen. Summing over all possible values of $k$ will tell us the total number of ways we can choose $r$ balls from $m+n$ balls.
