# Proof involving sums

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.

Homework Helper
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.

Last edited:
Homework Helper
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.