Proving $ {n + m \choose k } = {n \choose 0} {m \choose k} + {n \choose 1} {m \choose k - 1} + \cdots + {n \choose k} {m \choose 0} $ combinatorially

Question

Show that $$ {n + m \choose k } = {n \choose 0} {m \choose k} + {n \choose 1} {m \choose k - 1} + \cdots + {n \choose k} {m \choose 0} $$ and observe that $$ {2n \choose n} = \sum_{l=0}^n {n \choose l}^2 $$

Attempt.

I can see the second identity (or "observe") since if we put $m=k=n$, we have

$$ {2n \choose n} = {n \choose 0} {n \choose n} + {n \choose 1}{ n \choose n-1} + ... + {n \choose n }{n \choose 0} $$

and since ${i \choose k} = {i \choose i - k } $ we have the result.

However, I dont see how to prove the fist identity by using a combinatorial argument.

I can see that the LHF is the way of selecting a size k comittee out of $n+m$ students. I having trouble relating this to the RHS. Any pointers?

Answer 1

If you had to choose $k$ candies from $n$ different green candies and $m$ different red candies, how would you choose?

LHS -- You can put all the $n + m$ candies in a bag and then pick $k$ out of them. You have ${n + m \choose k}$ ways of doing this.

RHS -- You can $i$ candies from $n$ green candies and remaining $k-i$ from $m$ red candies. You have ${n \choose i} {m \choose k - i}$ ways of doing this. Now you add up for all values of $i$ from $0$ to $k$.

Answer 2

The RHS is simply adding the number of ways to choose

• 0 from the "left" size-$n$ committee and $k$ from the "right" size $m$-committee
• 1 from the left, $k-1$ from the right, etc. until
• $k$ from the left, 0 from the right

Together these partition the ways to select $k$ from both committees combined ($n+m$), hence the identity.

Answer 3

We have,

$$ (x+y)^{m+n}=(x+y)^m(x+y)^n $$

So, equating coefficient of $k$ on both sides, give,

$$ {n+m\choose k}=\sum_{i=0}^{k} {n\choose i}{m\choose {k-i}}$$

Individual terms on right side are product of coefficients of Binomial Series, and Binomial Series can be proved inductively. Further, coefficient equality on left and right above can be equated based based on induction.