# Binomial coefficient summation proof

## 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)n(1+x)m

## 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.

Related Precalculus Mathematics Homework Help News on Phys.org
Dick
Homework Helper
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?

The coefficient of x^l must be the same on both sides, right?
So that means l = j+k?

Dick
Homework Helper
So that means l = j+k?
Sure. Use that to reduce the double sum to a single sum.

How do I do that?

Dick