- #1

signalcarries

- 4

- 0

## Homework Statement

Prove that [tex]\sum_{k=0}^{l} \binom{n}{k} \binom{m}{l-k} = \binom{n+m}{l}[/tex]

## Homework Equations

If [tex]a[/tex] and [tex]b[/tex] are any numbers and [tex]n[/tex] is a natural number, then [tex](a+b)^{n}=\sum_{j=0}^{n} \binom{n}{j} a^{n-j}b^{j}[/tex]

## The Attempt at a Solution

I know that [tex](1+x)^{n}(1+x)^{m}=(1+x)^{n+m}[/tex] so that [tex]\sum_{k=0}^{n} \binom{n}{k}x^{k} \cdot \sum_{j=0}^{m} \binom{m}{j}x^{j} = \sum_{l=0}^{n+m} \binom{n+m}{l}x^{n+m}[/tex]

If I let [tex]j=l-k[/tex], then I get [tex]\sum_{k=0}^{n} \binom{n}{k}x^{k} \cdot \sum_{l=k}^{m+k} \binom{m}{l-k}x^{l-k} = \sum_{l=0}^{n+m} \binom{n+m}{l}x^{n+m}[/tex]

I can see that I'm close to the desired result--I'm just having trouble understanding how to get to it.