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.