1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Proof involving binomial coefficients.

  1. Mar 9, 2012 #1
    1. The problem statement, all variables and given/known data

    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

    2. Relevant equations

    3. 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.
  2. jcsd
  3. Mar 9, 2012 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Try looking at small values of l, so try to isolate (for example) the coefficients of x, x^2, x^3 and x^4 on both sides. That will help you see the patterns.

  4. Mar 9, 2012 #3
    I tried that, but I don't see how it shows any pattern. Isolating the coefficients is the part I'm having trouble with, whether or not L is a specific value.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook