Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
Quick question, how did you turn x^k into x^(l-j)? It "makes sense," but I'm not sure I would have come up with that. –  Josh Infiesto Jul 6 '12 at 18:59
    
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
    
Oh duh. Thanks. –  Josh Infiesto Jul 8 '12 at 19:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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