3
$\begingroup$

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.

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 5
    $\begingroup$ I'm pretty sure this same question has been posted several times. This is Vandermonde's identity. $\endgroup$ – Michael Hardy Jul 24 '15 at 19:11
  • $\begingroup$ There's something wrong with the RHS of your equation. $\endgroup$ – user230734 Jul 24 '15 at 19:11
  • $\begingroup$ 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. $\endgroup$ – Pedro Tamaroff Jul 24 '15 at 19:12
  • $\begingroup$ @mathlove : You link to a request for an algebraic rather than a combinatorial proof. That's not quite identical to this present question. $\endgroup$ – Michael Hardy Jul 24 '15 at 19:15
  • 1
    $\begingroup$ @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. $\endgroup$ – Winther Jul 24 '15 at 19:20
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Hint:

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.