How do I prove that $\sum\limits_{r=0}^k \binom{m}{r}\binom{n}{k-r} = \binom{m+n}{k}$ 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.  
 A: 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.
A: 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 
A: Hint:
Develop both sides of $\,(x+y)^m(x+y)^n=(x+y)^{m+n}$.
A: 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.
