Proof involving binomial coefficients.

[PKDfan]

Homework Statement

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

Homework Equations

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.

 

[Ray Vickson]

Homework Statement

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

Homework Equations

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.

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

 

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