1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof involving sums

  1. May 7, 2008 #1
    1. The problem statement, all variables and given/known data

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

    2. Relevant 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]

    3. 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.
     
  2. jcsd
  3. May 8, 2008 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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: May 8, 2008
  4. May 8, 2008 #3

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  5. May 8, 2008 #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.
     
  6. May 8, 2008 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proof involving sums
  1. A proof with sums (Replies: 0)

Loading...