Prove that $\sum_{k=0}^r {m \choose k} {n \choose r-k} = {m+n \choose r}$ Prove that $$\sum_{k=0}^r {m \choose k} {n \choose r-k} = {m+n \choose r}.$$
This problem is in the chapter about discrete random variables, but I have no idea what to go about substituting.
I can't get it to be a featured formula without screwing stuff up, sorry about that.
 A: Standard Binomial Coefficients
Use the Binomial Theorem
$$
\begin{align}
(1+x)^m(1+x)^n
&=\sum_{k=0}^m\binom{m}{k}x^k\sum_{j=0}^n\binom{n}{j}x^j\\
&=\sum_{k=0}^m\sum_{j=0}^n\binom{m}{k}\binom{n}{j}x^{k+j}\\
&=\sum_{k=0}^m\sum_{r=k}^{k+n}\binom{m}{k}\binom{n}{r-k}x^r&&j=r-k\\
&=\sum_{r=0}^{m+n}\color{#C00000}{\sum_{k=0}^r\binom{m}{k}\binom{n}{r-k}}x^r\tag{1}\\
(1+x)^{m+n}
&=\sum_{r=0}^{m+n}\color{#C00000}{\binom{m+n}{r}}x^r\tag{2}
\end{align}
$$
Compare coefficients of $x^r$ in $(1)$ and $(2)$.

Generalized Binomial Coefficients
As Michael Hardy mentions, the formula is true, even when $m$ and $n$ are not integers. The binomial coefficients can be generalized to any real number in the top argument:
$$
\binom{x}{k}=\frac{x(x-1)(x-2)\dots(x-k+1)}{k!}\tag{3}
$$
When $x$ is a negative integer, $(3)$ gives the formula for the negative binomial coefficients:
$$
\begin{align}
\binom{-n}{k}
&=\frac{-n(-n-1)(-n-2)\dots(-n-k+1)}{k!}\\
&=(-1)^k\frac{(n+k-1)(n+k-2)(n+k-3)\dots n}{k!}\\
&=(-1)^k\binom{n+k-1}{k}\tag{4}
\end{align}
$$
The Generalized Binomial Theorem states that for any real $m$,
$$
(1+x)^m=\sum_{k=0}^\infty\binom{m}{k}x^k\tag{5}
$$
Note that when $m$ is a non-negative integer, $\binom{m}{k}=0$ for $k\gt m$ and so $(5)$ is a polynomial in that case.
Using $(5)$, we can imitate the proof for the standard binomial coefficients:
$$
\begin{align}
(1+x)^m(1+x)^n
&=\sum_{k=0}^\infty\binom{m}{k}x^k\sum_{j=0}^\infty\binom{n}{j}x^j\\
&=\sum_{k=0}^\infty\sum_{j=0}^\infty\binom{m}{k}\binom{n}{j}x^{k+j}\\
&=\sum_{k=0}^\infty\sum_{r=k}^\infty\binom{m}{k}\binom{n}{r-k}x^r&&j=r-k\\
&=\sum_{r=0}^\infty\color{#C00000}{\sum_{k=0}^r\binom{m}{k}\binom{n}{r-k}}x^r\tag{6}\\
(1+x)^{m+n}
&=\sum_{r=0}^\infty\color{#C00000}{\binom{m+n}{r}}x^r\tag{7}
\end{align}
$$
Compare coefficients of $x^r$ in $(6)$ and $(7)$.
A: Notice that we set ${i \choose j} = 0$ whenever $0 \leq j \leq i$ is false. 
\begin{align}
\color{#ff0000}{\large\sum_{k = 0}^{\infty}{m \choose k}{n \choose r - k}}
&=
\sum_{k = 0}^{\infty}{m \choose k}\sum_{\ell = 0}^{n}{n \choose \ell}
\delta_{\ell, r - k}
=
\sum_{k = 0}^{\infty}{m \choose k}\sum_{\ell = 0}^{n}{n \choose \ell}
\oint_{\left\vert z\right\vert = 1}{{\rm d} z \over 2\pi{\rm i}}\,
{1 \over z^{\ell - r + k + 1}}
\\[3mm]&=
\oint_{\left\vert z\right\vert = 1}{{\rm d} z \over 2\pi{\rm i}}\,
{1 \over z^{1 - r}}
\sum_{k = 0}^{m}{m \choose k}\left(1 \over z\right)^{k}
\sum_{\ell = 0}^{n}{n \choose \ell}\left(1 \over z\right)^{\ell}
\\[3mm]&=
\oint_{\left\vert z\right\vert = 1}{{\rm d} z \over 2\pi{\rm i}}\,
{1 \over z^{1 - r}}\,\left(1 + {1 \over z}\right)^{m}
\left(1 + {1 \over z}\right)^{n}
\\[3mm]&=
\oint_{\left\vert z\right\vert = 1}{{\rm d} z \over 2\pi{\rm i}}\,
{1 \over z^{m + n -r + 1}}\,\left(1 + z\right)^{m + n}
=
\oint_{\left\vert z\right\vert = 1}{{\rm d} z \over 2\pi{\rm i}}\,
{1 \over z^{m + n -r + 1}}\sum_{k = 0}^{r + n}{r + n \choose k}z^{k}
\\[3mm]&=
\sum_{k = 0}^{m + n}{m + n \choose k}
\oint_{\left\vert z\right\vert = 1}{{\rm d} z \over 2\pi{\rm i}}\,
{1 \over z^{m + n - r + 1 - k}}
=
\sum_{k = 0}^{m + n}{m + n \choose k}\delta_{m + n - r,k}
\\[3mm]&=
{m + n \choose m + n - r}
=
\color{#ff0000}{\large{m + n \choose r}}
\end{align}
A: Think about picking a subsets of size $r$ from a set of size $m+n$. You can simply choose it, and you can do it in 

$${m+n} \choose r$$ 

ways, or you can first choose a subset of size $k$ of $m$ and then a subset of size $r-k$ of $n$. And you can do this for $k=0,1,\ldots,r$ in 

$${m \choose k }{n \choose r-k}$$ 

ways.
A: Vandermonde's identity
$$
\sum_{k=0}^r {m \choose k} {n \choose r-k} = {m+n \choose r}
$$
is actually true even when $m$ and $n$ are not integers.  But just suppose you have a committee in the Senate consisting of $m$ Democrats and $n$ Republicans.  The number of ways to choose a subcommittee of $r$ senators is
$$
\sum_{k=0}^r\Big(\text{the number of ways to choose $k$ Democrats AND $r-k$ Republicans}\Big).
$$
You should associate the word "and" with multiplication.
As far as I know, one must resort to other methods when $m$ or $n$ is not an integer or is negative.
PS: When $m$ is not an integer or is negative then $\dbinom m k$ is defined as
$$
\frac{m(m-1)(m-2)\cdots(m-k+1)}{k!}.
$$
When $m$ is a nonnegative integer, then this is the same as $\dfrac{m!}{k!(m-k)!}$.
