# Proof involving binomial coefficients.

1. Mar 9, 2012

### PKDfan

1. The problem statement, all variables and given/known data

Prove that
$\sum\limits_{k=o}^l {n \choose k}{m \choose l-k} = {n+m \choose l}$

Hint: Apply binomial theorem to (1+x)^n * (1+x)^m

2. Relevant equations

3. The attempt at a solution

Using the hint, I started by saying that (1+x)^n * (1+x)^m = (1+x)^(n+m)

= $\sum\limits_{k=o}^n {n \choose k}x^k * \sum\limits_{j=o}^m {m \choose j}x^j = \sum\limits_{l=o}^{n+m} {n+m \choose l}x^l$

I then rewrote that as a double sum:

$\sum\limits_{k=o}^n \sum\limits_{j=o}^m {n \choose k} {m \choose j}x^{k+j} = \sum\limits_{l=o}^{n+m} {n+m \choose l}x^l$

= $\sum\limits_{k=o}^n \sum\limits_{l-k=o}^m {n \choose k} {m \choose l-k}x^l = \sum\limits_{l=o}^{n+m} {n+m \choose l}x^l$

I have no idea where to proceed from here. Is there some way to divide out one of the sums, maybe? I've been thinking about this for hours and I can't figure it out.

2. Mar 9, 2012

### Ray Vickson

Try looking at small values of l, so try to isolate (for example) the coefficients of x, x^2, x^3 and x^4 on both sides. That will help you see the patterns.

RGV

3. Mar 9, 2012

### PKDfan

I tried that, but I don't see how it shows any pattern. Isolating the coefficients is the part I'm having trouble with, whether or not L is a specific value.