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 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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook