- #1
PKDfan
- 19
- 0
Homework Statement
Prove that
[itex]\sum\limits_{k=o}^l {n \choose k}{m \choose l-k} = {n+m \choose l}[/itex]
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)
= [itex]\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[/itex]
I then rewrote that as a double sum:
[itex]\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[/itex]
= [itex]\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[/itex]
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.