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!

Applying binomial theorem to prove combinatorics identity

  1. Dec 13, 2015 #1
    1. The problem statement, all variables and given/known data
    Prove that [tex] \sum\limits_{k=0}^l{n \choose k}{m \choose l-k} = {n+m \choose k}[/tex]


    2. Relevant equations
    Binomial theorem

    3. The attempt at a solution

    We know that [tex] (1+x)^n(1+x)^m = (1+x)^{n+m} [/tex]
    which, by the binomial theorem, is equivalent to:
    [tex] {\sum\limits_{k=0}^n{n \choose k}x^k}{\sum\limits_{j=0}^m{m \choose j}x^j} = {\sum\limits_{l=0}^{n+m}{n+m \choose l}x^l} [/tex]
    The solution involves setting [tex] l = j+k [/tex] and then simplifying the left side to:
    [tex] {\sum\limits_{k=0}^l{n \choose k}{m \choose l-k}x^l} [/tex] but I cant see how this is in any way rigorously justified. Can someone help me see the justification for simplifying the left side? Thanks.
     
  2. jcsd
  3. Dec 13, 2015 #2

    SteamKing

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    Have you tried applying the definition of ##{n \choose k} = \frac{n!}{k!(n-k)!}## to the terms in the summations?
     
  4. Dec 13, 2015 #3

    nrqed

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    The key point is that this must be true for any value of x, which implies that the two sides must be equal for each choice of power of x. That means that the identity can be made much stronger by imposing the equality for each separate power of x. So the coefficient of x to some power on one side must be equal to the coefficient of the term with the same power of x on the other side, this leads to your result with j+k=l.
     
  5. Dec 13, 2015 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Are you saying you do not understand why
    [tex] \sum_k c_k x^k \; \sum_j d_j x^j = \sum_l \left(\sum_k c_k d_{l-k} \right) x^l \;? [/tex]
    It is a standard result in elementary algebra. All you are doing is gathering together the coefficients of ##x^k \cdot x^j =x^{k+j}## for each constant value of ##l = k+j##.
     
  6. Dec 13, 2015 #5

    SteamKing

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    All I know is that:

    It seems to me, from a purely uninformed point of view, that bringing the binomial theorem into this proof just complicates things.
     
  7. Dec 13, 2015 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    As I understand the OP, the object of the exercise is to use the binomial theorem to establish the identity. Whether there is a better way is beside the point.
    Specifically, the question is how the product of the two sums collapses to the single sum, k=0 to l.
    @Orange-Juice , the method sets l=j+k, so j=l-k. Substitute that in the summation, rewrite it as a double sum, and change the order of the summation.
    Note that you are wrong about what the left hand side needs to become. You missed an enclosing ##\Sigma_{l=0}^{n+m}##
     
  8. Dec 13, 2015 #7

    SteamKing

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    That's just it. The problem statement simply says, "Prove such and such." It doesn't say "Using the binomial theorem, prove such and such."

    I think the OP has just thrown the binomial theorem in because he doesn't have anything else to put in Section 2 of the HW template. The summations don't even involve binomials.
     
  9. Dec 13, 2015 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    The OP says "the solution involves setting...". Either that is a hint provided (in conjunction with a hint or direction to use the binomial theorem), or OJ is trying to follow a solution that uses the binomial theorem. Either way, the question OJ presents is how a particular step works.
     
  10. Dec 14, 2015 #9

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Using the binomial expansion to prove the result is the more-or-less standard way of doing it; it is the first thing I would have done if I were asked to prove the identity. The close connection between the "binomial coefficients" and the "binomial expansion" cries out to be used.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Applying binomial theorem to prove combinatorics identity
  1. Binomial Theorem (Replies: 9)

  2. Binomial theorem (Replies: 4)

  3. Binomial theorem (Replies: 3)

Loading...