# Help with binomial theorem related proof

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.

-
Concrete Mathematics by Graham, Knuth, and Patashnik is good for this sort of thing. – MJD Jul 5 '12 at 2:15
Grawr. It's so expensive, though it's been on my wishlist for a while... – Josh Infiesto Jul 6 '12 at 18:58

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.
I want to multiply the $x^j$ in the first sum by something in the second sum to get $x^{\ell}$. $(x^j)(x^{\rm something})=x^{\ell}$ implies ${\rm something\ }=\ell-j$. – Gerry Myerson Jul 7 '12 at 5:31