Proving Sums Involving Binomial Coefficients

[signalcarries]

Homework Statement

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

Homework Equations

If $$a$$ and $$b$$ are any numbers and $$n$$ is a natural number, then $$(a+b)^{n}=\sum_{j=0}^{n} \binom{n}{j} a^{n-j}b^{j}$$

The Attempt at a Solution

I know that $$(1+x)^{n}(1+x)^{m}=(1+x)^{n+m}$$ so that $$\sum_{k=0}^{n} \binom{n}{k}x^{k} \cdot \sum_{j=0}^{m} \binom{m}{j}x^{j} = \sum_{l=0}^{n+m} \binom{n+m}{l}x^{n+m}$$

If I let $$j=l-k$$, then I get $$\sum_{k=0}^{n} \binom{n}{k}x^{k} \cdot \sum_{l=k}^{m+k} \binom{m}{l-k}x^{l-k} = \sum_{l=0}^{n+m} \binom{n+m}{l}x^{n+m}$$

I can see that I'm close to the desired result--I'm just having trouble understanding how to get to it.

 

[Dick]

You have some index problems. In your final solution l is a dummy index (twice). In your original problem it's not. If you fix this I think you will see the solution. You aren't as close as you think, nor are you as far away as you think.

 

[Dick]

The dummy problem is coming because when you set l=j+k you are actually saying 'pick the x^l term' from the right side (where the power of x should have been x^l, not x^(n+m)). Since you are selecting a specific l, the sum goes away on the right. The constrain l=j+k will also get rid of one of the sums on the left.

 

[signalcarries]

OK, so I am picking a specific value for l by choosing l=j+k, although this still seems a little strange to me, since I am summing over j and k on the LHS. Is it kind of like a function where I input two values (some j and some k) on the LHS, giving me a value on the RHS?

I can see that two of the sums will disappear. I think this leaves me with:
$$\sum_{k=0}^{n} \binom{n}{k} \binom{m}{l-k} x^{l} = \binom{n+m}{l}x^{l}$$

I'm still having trouble seeing why my final sum runs from 0 to l.

 

[Dick]

What you are really doing is picking off the x^l term on both sides. If two polynomials in x are equal for all x, then coefficients of each power of x are equal on both sides. If k>l in the first sum, then it doesn't contribute.