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 jm\choose kx^{j+k} = \sum^{n+m}_{l=0}n+m \choose lx^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.