$\begingroup$

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.

$\endgroup$ 2

4 Answers

$\begingroup$

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)$.

$\endgroup$ $\begingroup$

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}

$\endgroup$ 4 $\begingroup$

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.

$\endgroup$ 3 $\begingroup$

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)!}$.

$\endgroup$