1
$\begingroup$

I'm currently working through Spivak on my own. I'm stuck on this proof, and the answer key is extremely vague on this problem. I think I'm missing a manipulation involving sums.

Prove that $\displaystyle\sum_{k=0}^{l}\dbinom{n}{k}\dbinom{m}{l-k}= \dbinom{n+m}{l}$.

As a hint, he gives "Apply the binomial theorem to $\displaystyle(1+x)^n(1+x)^m$"

Following the hint, I get:

$\displaystyle(1+x)^n(1+x)^m=(1+x)^{n+m}$

Applying the binomial theorem, we get:

$\displaystyle\sum_{j=0}^n\dbinom{n}{j}x^j\cdot\sum_{k=0}^m\dbinom{n}{k}x^k=\sum_{l=0}^{n+m}\dbinom{n+m}{l}x^l$

Here's where I get stuck. How do I manipulate this into looking like the above?

As an aside, this is not homework. I'm working through the book for my own benefit. I'm usually reticent about consulting the answer key, but I've been stuck on this one for about a day.

  • 0
    Grawr. It's so expensive, though it's been on my wishlist for a while...2012-07-06

1 Answers 1

4

Starting where you got stuck, how do you get a term in $x^{\ell}$ from the product on the right side? You get it when you multiply ${n\choose j}x^j$ from the first term with ${m\choose\ell-j}x^{\ell-j}$ from the second term. [Note that you have a typo, an $n$ in the second sum where you wanted to have $m$] So, the coefficient of $x^{\ell}$ is the sum of all the terms ${n\choose j}{m\choose\ell-j}$, as desired.

  • 0
    Oh duh. Thanks.2012-07-08