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!

Summation problem

  1. Feb 6, 2006 #1
    i have to prove that:

    n
    sum [C(n,k)]^2=C(2n,n)
    k=0
    i have in my text a hint that i need to use:

    (1+x)^n(1+x)^n=(1+x)^2n
    but i got that:

    n 2n
    sum [C(n,k)]^2= sum [C(2n,k)]
    k=0 k=0

    how do i get out of this mess?
     
  2. jcsd
  3. Feb 6, 2006 #2
    it should be
    2n
    sum C(2n,n)
    k=0

    but i reackon you understood me the first time.
     
  4. Feb 6, 2006 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Of course, you know that [itex](1+ x)^n= \sum_{i=0}^n _nC_i x^i[/itex] (the binomial theorem). What are the coefficients of (1+x)n(1+x)n in terms of nCi?
     
  5. Feb 6, 2006 #4
    2n_C_i

    but still it the summation sign stays, unless i open it this way:

    2n_C_1+2n_C_2+...+2n_C_2n
    am i wrong here completely?
     
  6. Feb 6, 2006 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Notice that you are multiplying two sums together.
    (a+ bx+ cx2)(u+ vx+ wx2)= au+ avx+ awx2+ bux+ bvx2+ bwx3+ cux2+ cvx3+ cwx4= au+ (av+bu)x+ (aw+ bv+ cu)x2+ (bw+ cv)x3+ cwx4.

    Each coefficient is a sum.
     
  7. Feb 7, 2006 #6
    but here we have (1+2x+x^2)^n=(1+(2x+x^2))^n=
    n
    =sum n_C_k (2x+x^2)^k
    k=0

    when x=1

    n
    sum (n_C_k)*3^k= (n_C_0)+3*(n_C_1)+...+3^n
    k=0

    now how do i get from this, the final answer:
    2n_C_n
    ?
     
  8. Feb 7, 2006 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    [tex]\binom{2n}{n}[/tex]

    is the coefficient of x^n in the expansion of (1+x)^{2n}

    that is all the hint you need (oh, and to possibly forget what you'd done and start again).
     
  9. Feb 7, 2006 #8

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Are you allowed to give arguments about how the left side represents the number of ways to make some choice, and show tha the right side represents the same thing, thereby proving that both quantities are equal? The number of ways to choose n objects from a set of 2n is equal to the number of ways to:

    choose 0 from the first n AND then n from the second n
    OR
    choose 1 from the first n AND then n-1 from the second n
    OR
    .
    .
    .
    OR
    choose k from the first n AND n-k from the second n
    OR
    .
    .
    .
    OR
    choose n from the first n AND choose 0 from the second n

    =

    choose 0 from the first n AND then 0 from the second n
    OR
    choose 1 from the first n AND then 1 from the second n
    OR
    .
    .
    .
    OR
    choose k from the first n AND k from the second n
    OR
    .
    .
    .
    OR
    choose n from the first n AND choose n from the second n

    since the number of ways to choose n-k elements from n is the same as the number of ways to choose k.
     
  10. Feb 8, 2006 #9
    i know that
    2n
    (1+x)^2n=sum (2n_C_k)x^k
    k=0

    but how do i get the coeffient only, that's my big q?
     
  11. Feb 8, 2006 #10

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    what does 'get the coefficient' mean?

    Write down the expression in two different ways, equate coefficients.

    EXAMPLE.

    (1+x)^4 = 1+4x+10x^2+4x^3+x^4 here are the 4Cr

    it also equals ((1+x)^2)^2=(1+x+x^2)^2=(2C0+2C1x + 2C0x^2)^2

    now can you see how to find the coeffiecients in two different ways?
     
  12. Feb 8, 2006 #11

    benorin

    User Avatar
    Homework Helper

    [tex](1+x)^n=\sum_{k=0}^{n} _nC_kx^k[/tex] and [tex](1+x)^{2n}=\sum_{k=0}^{2n} _{2n}C_kx^k[/tex]

    and since [tex](1+x)^n(1+x)^n=(1+x)^{2n}[/tex] we have

    [tex](1+x)^n(1+x)^n=\left( \sum_{k=0}^{n} _nC_kx^k\right) \left( \sum_{j=0}^{n} _nC_jx^j\right) = \sum_{k=0}^{2n} _{2n}C_kx^k = (1+x)^{2n}[/tex]

    from here, multiply out

    [tex]\left( \sum_{k=0}^{n} _nC_kx^k\right) \left( \sum_{j=0}^{n} _nC_jx^j\right)[/tex]

    to get a sum of the form

    [tex]\sum_{k=0}^{2n} a_kx^k[/tex]

    where you need to figure out what the ak's are. It then follows that, equating coefficients of like powers of x, we must have

    [tex]a_k= _{2n}C_k[/tex].
     
  13. Feb 8, 2006 #12
    now i get it.
    it took time, but thanks matt and halls, and also the new guy, benorin.
    (-:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Summation problem
  1. Summation problem (Replies: 3)

  2. Summation problem (Replies: 2)

  3. Summation problem (Replies: 5)

  4. Summation Problem (Replies: 7)

  5. Summation problem (Replies: 4)

Loading...