# How do I prove that $\sum\limits_{r=0}^k \binom{m}{r}\binom{n}{k-r} = \binom{m+n}{k}$ [duplicate]

I have tried the following: Expanding the coefficients and i end up with something like this: $\sum\limits_{r=0}^k \binom{m}{r}\binom{n}{k-r} = \frac{m!}{(m-r)!r!} \frac{n!}{(n-k+r)!(k-r)!}$ and then expand the sum which does not seem to be very useful. I have also been thinking about use the Pascal's triangle in my proof but i haven't figured out how to do it in a way that does not look so sloppy. Any tips will be appreciated.

## marked as duplicate by mathlove, Winther, Aaron Maroja, Community♦Jul 24 '15 at 19:33

• I'm pretty sure this same question has been posted several times. This is Vandermonde's identity. – Michael Hardy Jul 24 '15 at 19:11
• There's something wrong with the RHS of your equation. – user230734 Jul 24 '15 at 19:11
• There is a standard counting argument: to pick a $k$ subset out of a set of $m+n$ elements, choose for each $r$, an $r$ subset of the first $m$ elements and a $k-r$ subset of the remaining $n$ elements. – Pedro Tamaroff Jul 24 '15 at 19:12
• @mathlove : You link to a request for an algebraic rather than a combinatorial proof. That's not quite identical to this present question. – Michael Hardy Jul 24 '15 at 19:15
• @MichaelHardy Nowhere in the question is a combinatorial proof asked for. It simply ask "How do I prove this" so imo the duplicate it fine unless OP adds more info about what he wants. – Winther Jul 24 '15 at 19:20

The right side is the number of ways to choose a subcommittee of size $k$ from a committee of $m$ Democrats and $n$ Republicans.

$\dbinom{m}{r}\dbinom{n}{k-r}$ is the number of ways to choose $r$ Democrats and $k-r$ Republicans from that committee. The number $r$, the number of Democrats, plainly has to be at least $0$ and not more than $k$. So $k-r$, the number of Republicans, must also be in that range. Now think about what it means to take the sum.

Hint:

Develop both sides of $\,(x+y)^m(x+y)^n=(x+y)^{m+n}$.

If you want to use Pascal's Triangle, then I would suggest induction on $n$.

In the induction step, working right to left, first use the triangle property to split $\binom{m+n}{k}$ into $\binom{m+(n-1)}{k-1}+\binom{m+(n-1)}{k}$, then apply the induction hypothesis to each of these binomial coeffients. Finally collect terms with the same $\binom{m}{r}$ and use the triangle again to combine their coefficients.

choosing $k$ people from $m+n$ people $=\binom{m+n}{k}$
now suppose :choosing $k$ people from $m\text{ people} + n\text{ people}$
choose $0$ from $m$ , $k$ from $n$
choose $1$ from $m$ , $k-1$ from $n$
choose $2$ from $m$ , $k-2$ from $n$
${}\qquad\vdots$
in left hand we have :$$\binom{m}{0}\binom{n}{k}+\binom{m}{1}\binom{n}{k-1}+\binom{m}{2}\binom{n}{k-2}+\cdots+\binom{m}{k}\binom{n}{k-k}$$ and in the right hand we have $$\binom{m+n}{k}$$ so
they must be equal