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?

Here is a short inductive proof, that may however not be as illuminating as a combinatorial argument:
Theorem.
For all nonnegative integers $r$, $m$ and $n$, there holds Vandermonde's
identity
$$
\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}.
$$
Proof.
Let $f(m,n,r)=\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}$, and use the
convention that $\binom{m}{k}=0$ unless $0\leq k\leq m$. Note that
$f(0,n,r)=\binom{n}{r}$. Assume now that
$$
f(m,n,r)=\binom{m+n}{r}
$$
for fixed $m$, and for all $n$ and $r$. From this and from Pascal's rule
$\binom{m+1}{k}=\binom{m}{k-1}+\binom{m}{k}$, we find
\begin{eqnarray*}
f(m+1,n,r)&=&f(m,n,r-1)+f(m,n,r) \\
&=&\binom{m+n}{r-1}+\binom{m+n}{r}=\binom{m+n+1}{r}.\Box
\end{eqnarray*}
