Binomial coefficient summation proof

  • Thread starter zeion
  • Start date
  • #1
467
0

Homework Statement



Prove that

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

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

Homework Equations





The Attempt at a Solution



I apply the hint to that thing to get [tex] \sum^{n}_{j=0}[/tex] [tex] n \choose j [/tex] [tex]x^j \sum^{m}_{k=0}[/tex] [tex] m \choose k [/tex] [tex]x^k [/tex]


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

Now I am stuck.
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,258
619
The coefficient of x^l must be the same on both sides, right? That gives you C(n+m,l) on the right. What terms on the left make a power of x^l?
 
  • #3
467
0
The coefficient of x^l must be the same on both sides, right?
So that means l = j+k?
 
  • #4
Dick
Science Advisor
Homework Helper
26,258
619
So that means l = j+k?
Sure. Use that to reduce the double sum to a single sum.
 
  • #5
467
0
How do I do that?
 
  • #6
Dick
Science Advisor
Homework Helper
26,258
619
How do I do that?
For each value of j there is only one value of k such that j+k=l. Just sum over j and express k in terms of l and j.
 

Related Threads on Binomial coefficient summation proof

Replies
3
Views
625
  • Last Post
Replies
1
Views
6K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
6
Views
697
Replies
10
Views
769
  • Last Post
Replies
2
Views
1K
Replies
1
Views
652
Replies
5
Views
1K
Top