Verify the following combinatorial identity: $\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$

Question

$$\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?

Answer 1

Note that there exist different $m+n$ balls and two bags.

One bag contains $m$ balls and the other has $n$.

What is the number of choosing $r$ balls ? Clearly $$ _{m+n}C_r$$

But we divided into two bag. : The number of choosing $k$ balls in the first bag is $ _mC_k $ And we must choose $r-k$ balls in second. The number of possibility is $ _nC_{r-k}$ So we have $$ _mC_k\ _nC_{r-k}$$

Answer 2

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.

Answer 3

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*}

Answer 4

Using the binomial theorem, we have $$ \begin{align} (1+x)^m(1+x)^n &=\sum_{j=0}^m\binom{m}{j}x^j\sum_{k=0}^n\binom{n}{k}x^k\\ &=\sum_{k=0}^{m+n}\color{#C00000}{\sum_{j=0}^k\binom{m}{j}\binom{n}{k-j}}x^k \end{align} $$ and $$ \begin{align} (1+x)^{m+n} &=\sum_{k=0}^{m+n}\color{#C00000}{\binom{m+n}{k}}x^k \end{align} $$ Compare the coefficients of $x^k$.

Answer 5

An other way to proceed is to write:

$ (x+1)^{m+n} = (x+1)^n*(x+1)^m $

Then you develop each term using the binomial formula and you evaluate the coefficient of the term $x^r$ on the right, knowing that the one on the left is $C_{n+m}^r$. The proof is quite straightforward when you go down this path.

You get a double sum with two index i,j and to find the coefficient of $x^r$ you take each term that verifies i+j=r .

Does that help?