Proof involving sums

  • #1

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.
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,260
619
You have some index problems. In your final solution l is a dummy index (twice). In your original problem it's not. If you fix this I think you will see the solution. You aren't as close as you think, nor are you as far away as you think.
 
Last edited:
  • #3
Dick
Science Advisor
Homework Helper
26,260
619
The dummy problem is coming because when you set l=j+k you are actually saying 'pick the x^l term' from the right side (where the power of x should have been x^l, not x^(n+m)). Since you are selecting a specific l, the sum goes away on the right. The constrain l=j+k will also get rid of one of the sums on the left.
 
  • #4
OK, so I am picking a specific value for l by choosing l=j+k, although this still seems a little strange to me, since I am summing over j and k on the LHS. Is it kind of like a function where I input two values (some j and some k) on the LHS, giving me a value on the RHS?

I can see that two of the sums will disappear. I think this leaves me with:
[tex]\sum_{k=0}^{n} \binom{n}{k} \binom{m}{l-k} x^{l} = \binom{n+m}{l}x^{l}[/tex]

I'm still having trouble seeing why my final sum runs from 0 to l.
 
  • #5
Dick
Science Advisor
Homework Helper
26,260
619
What you are really doing is picking off the x^l term on both sides. If two polynomials in x are equal for all x, then coefficients of each power of x are equal on both sides. If k>l in the first sum, then it doesn't contribute.
 

Related Threads on Proof involving sums

Replies
3
Views
1K
Replies
4
Views
1K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
5
Views
5K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
7
Views
1K
  • Last Post
2
Replies
43
Views
4K
  • Last Post
Replies
2
Views
780
  • Last Post
Replies
4
Views
1K
Top