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 using binomial theorem

  1. Jan 22, 2009 #1
    I am asked to prove that [tex] \sum ^n _{k=0} (C^n_k)^2 = C^{2 n}_n[/tex]

    Where [tex] C^n_k [/tex] signifies "n choose k"

    I am told the hint to use the binomial theorem and to calculate the coefficient of x^n in the product [tex](1+x)^n (1+x)^n = (1+x)^{2n}[/tex]

    the Binomial theorem is given by [tex] (x+y)^n = \sum_{k=0} ^n C_k^n x^{n-k} y^k [/tex]

    Following the hint, we see that:

    [tex](1+x)^n = \sum^n _{k=0} C^n _k x^{n-k} [/tex]

    [tex](1+x)^{2n} = \sum^{2n} _{k=0} C^{2n} _k x^{2n-k} [/tex]

    I believe from here, I would like to show that:

    [tex]\left( \sum^n _{k=0} C^n _k x^{n-k} \right) \left( \sum^n _{k=0} C^n _k x^{n-k} \right) = \sum^{2n} _{k=0} C^{2n} _k x^{2n-k}[/tex]

    And ultimately, I believe the goal is to get [tex] \sum ^n _{k=0} (C^n_k)^2 = C^{2 n}_n[/tex] from the above relation but I'm not sure where to go from here.

    Any ideas?
     
  2. jcsd
  3. Jan 22, 2009 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You can also write that as:
    [tex]
    \left( \sum^n _{k=0} C^n _k x^{n-k} \right) \left( \sum^n _{j=0} C^n _j x^{j} \right) = \sum^{2n} _{k=0} C^{2n} _k x^{2n-k}
    [/tex]
    The terms that produce a x^n on the left are the ones where k=j, yes? Write it as a single sum. Now look for the x^n on the right. Two polynomials can only be equal if the coefficients of each power of x are the same.
     
  4. Jan 22, 2009 #3
    I'm still confused as to what was written.

    I believe you meant to write:
    [tex]

    \left( \sum^n _{k=0} C^n _k x^{n-k} \right) \left( \sum^n _{j=0} C^n _j x^{n-j} \right) = \sum^{2n} _{k=0} C^{2n} _k x^{2n-k}
    [/tex]

    I'm not sure what "The terms that produce a x^n" exactly means, which is why I dont understand the restriction k=j.

    Are you saying:

    [tex]

    \sum^n _{k=0} C^n _k x^{n-k} C^n _k x^{n-k} = \sum^{2n} _{k=0} C^{2n} _k x^{2n-k}
    [/tex]

    ? Im not sure I follow, could you please explain?
     
  5. Jan 22, 2009 #4

    gabbagabbahey

    User Avatar
    Homework Helper
    Gold Member

    Using the binomial theorem,

    [tex](x+y)^n = \sum_{k=0} ^n C_k^n x^{n-k} y^k[/tex]

    you can write [itex](1+x)^n[/itex] in two different ways:

    (1)Setting [itex]x\to x[/itex] and [itex]y\to 1[/itex] you get

    [tex](1+x)^n = \sum^n _{k=0} C^n _k x^{n-k} [/tex]

    (2)Setting [itex]x\to 1[/itex] and [itex]y\to x[/itex] you get

    [tex](1+x)^n = \sum^n _{k=0} C^n _k x^{k}=\sum^n _{j=0} C^n _j x^{j} [/tex]

    That means you can write:

    [tex](1+x)^n(1+x)^n=\left( \sum^n _{k=0} C^n _k x^{n-k} \right) \left( \sum^n _{j=0} C^n _j x^{j} \right)[/tex]

    And so, the expression Dick gave is perfectly valid.

    Since the two summations on the LHS of that expression are over different indices, you can rewrite the product as:

    [tex]\left( \sum^n _{k=0} C^n _k x^{n-k} \right) \left( \sum^n _{j=0} C^n _j x^{j} \right)= \sum^n _{j,k=0} (C^n _k x^{n-k})(C^n _j x^{j})[/tex]
     
  6. Jan 22, 2009 #5
    Ah, I see the step that was skipped. Thanks for clarification.

    [tex] \sum^n _{j,k=0} (C^n _k x^{n-k})(C^n _j x^{j}) = \sum^{2n} _{k=0} C^{2n} _k x^{2n-k} [/tex]

    We want the coefficient of each power to be the same since the polynomials are the same...

    However, x^{n-k} x^{j} and x^{2n-k} do not match, I'm trying to think of a way but Im not good with the various indices, is there a way to combine j and k? Since we are using one summation, why not just make j=k and have one summation?
     
  7. Jan 23, 2009 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Not every term can give an x^n. The power in the terms on the left is x^(n-k+j). That's equal to x^n only if k=j.
     
  8. Jan 23, 2009 #7
    But how does that help match the right hand side of x^{2n-k}?
     
  9. Jan 23, 2009 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    The only term in the sum on the right that is x^n is the one where k=n.
     
  10. Jan 23, 2009 #9
    [tex]
    \sum^n _{j,k=0} (C^n _k x^{n-k})(C^n _j x^{j}) = \sum^{2n} _{k=0} C^{2n} _k x^{2n-k} [/tex]

    LHS: let j=k
    RHS: let k=n

    [tex]
    \sum^n _{k=0} (C^n _k C^n _k x^{n}) = \sum^{2n} _{n=0} C^{2n} _n x^{n} [/tex]

    for the polynomials to be equal, we must have the same coefficients, so can we say that:

    since [tex]\sum_{n=0} ^{2n} =1[/tex] because n=0 then

    [tex]
    x^n \sum^n _{k=0} (C^n _k C^n _k ) = x^n C^{2n} _n [/tex]

    on LHS we can bring the x^n out because it doesnt depend on k

    [tex]
    \sum^n _{k=0} (C^n _k C^n _k ) = C^{2n} _n [/tex]

    is this a proper conclusion?
     
  11. Jan 23, 2009 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    [tex]

    \sum^n _{k=0} (C^n _k C^n _k x^{n}) = \sum^{2n} _{n=0} C^{2n} _n x^{n}
    [/tex]

    There is no summation on the right side. You want to pick out the only term that contains x^n. So,

    [tex]

    \sum^n _{k=0} (C^n _k C^n _k x^{n}) = C^{2n} _n x^{n}
    [/tex]

    There's not much need to argue after that.
     
  12. Jan 23, 2009 #11
    Why is there no summation on the right side? Is it because n=0?
     
  13. Jan 23, 2009 #12

    gabbagabbahey

    User Avatar
    Homework Helper
    Gold Member

    It's because you've picked out a single term in the series; the one that is of order [itex]x^n[/itex]. That corresponds to the k=n term. You are not looking at the other 2n-1 terms where k≠n.

    Likewise on the LHS; you are only looking at the terms that is of order [itex]x^n[/itex]. That corresponds to the j=k term, so in the summation over j, you look only at the term where j=k.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proof using binomial theorem
Loading...