5
$\begingroup$

I'm having some trouble with the following proof: $$\sum^k_{a=0} {{n}\choose{a}}{{m}\choose{k-a}} = {{n+m}\choose{k}}$$

I'm trying to prove this to learn a couple of things about the Pascal's triangle. I don't know where to start on the proof. I have tried expanding both sides using the binomial coefficient property but have had no luck.

$\endgroup$

marked as duplicate by David K, Daniel W. Farlow, hardmath, Ben Sheller, Kamil Jarosz Apr 11 '16 at 14:23

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.

  • $\begingroup$ This is Vandermonde's Identity and has been asked about several times on this site already. Here is one such link. There is likely a better link to use to mark as duplicate however. $\endgroup$ – JMoravitz Apr 10 '16 at 21:29
  • $\begingroup$ @JMoravitz I didn't know the name of the identity, otherwise I would have just googled it. Thanks $\endgroup$ – TheSalamander Apr 10 '16 at 21:32
5
$\begingroup$

This is called Vandermonde's identity. To prove it, write $(1+x)^{n+m}=(1+x)^n(1+x)^m$ and look at the coefficient of $x^k$ on both sides.

$\endgroup$
  • $\begingroup$ Thank you. I was having some trouble finding this identity online! $\endgroup$ – TheSalamander Apr 10 '16 at 21:30
5
$\begingroup$

Suppose you need to choose $k$ elements out of a possible $n+m$. Divide the total list into the first $n$ and the remaining $m$. Your choice must consist of $a$ from the first part (where $a\in \{0,\cdots k\}$) and $k-a$ from the second part. Conversely, any two such collections combine to give you a viable collection of $k$.

$\endgroup$
4
$\begingroup$

The RHS counts the number of ways of selecting a committee of $k$ people from $n$ women and $m$ men.

The expression $$\binom{n}{a}\binom{m}{k - a}$$ counts the number of ways of selecting a committee of $k$ people consisting of $a$ women and $k - a$ men selected from selected from a group consisting of $n$ women and $m$ men. Thus, the summation on the LHS counts all the ways of selecting a committee of $k$ people can be selected from $n$ women and $m$ men.

$\endgroup$

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