- #1

Orange-Juice

- 8

- 0

## Homework Statement

Prove that [tex] \sum\limits_{k=0}^l{n \choose k}{m \choose l-k} = {n+m \choose k}[/tex]

## Homework Equations

Binomial theorem

## The Attempt at a Solution

[/B]

We know that [tex] (1+x)^n(1+x)^m = (1+x)^{n+m} [/tex]

which, by the binomial theorem, is equivalent to:

[tex] {\sum\limits_{k=0}^n{n \choose k}x^k}{\sum\limits_{j=0}^m{m \choose j}x^j} = {\sum\limits_{l=0}^{n+m}{n+m \choose l}x^l} [/tex]

The solution involves setting [tex] l = j+k [/tex] and then simplifying the left side to:

[tex] {\sum\limits_{k=0}^l{n \choose k}{m \choose l-k}x^l} [/tex] but I can't see how this is in any way rigorously justified. Can someone help me see the justification for simplifying the left side? Thanks.