Binomial coefficient summation proof

[zeion]

Homework Statement

Prove that

$$\sum^{l}_{k=0}$$ $$n \choose k$$ $$m \choose l-k$$ = $$n+m \choose l$$

Hint: Apply the binomial theorem to (1+x)ⁿ(1+x)^m

Homework Equations

The Attempt at a Solution

I apply the hint to that thing to get $$\sum^{n}_{j=0}$$ $$n \choose j$$ $$x^j \sum^{m}_{k=0}$$ $$m \choose k$$ $$x^k$$= $$\sum^{n}_{j=0}\sum^{m}_{k=0}$$$$n\choose j$$$$m\choose k$$$$x^{j+k} = \sum^{n+m}_{l=0}$$$$n+m \choose l$$$$x^l$$

Now I am stuck.

 

[Dick]

The coefficient of x^l must be the same on both sides, right? That gives you C(n+m,l) on the right. What terms on the left make a power of x^l?

 

[zeion]

The coefficient of x^l must be the same on both sides, right?

So that means l = j+k?

 

[Dick]

So that means l = j+k?

Sure. Use that to reduce the double sum to a single sum.

 

[zeion]

How do I do that?

 

[Dick]

How do I do that?

For each value of j there is only one value of k such that j+k=l. Just sum over j and express k in terms of l and j.