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!

Prove the equation using Newton's binom

  1. Jan 7, 2017 #1
    1. The problem statement, all variables and given/known data
    prove that sum C(2n,k)*k = n*2^(2n-1); k=0,n

    2. Relevant equations
    (x+y)^n = sum [C(n,k)*x^k*y^(n-k)]; k=0,n. // 1
    in // 1, when y=1: (1+x)^n = sum [C(n,k)*x^k]; k=0,n // 2
    in // 2, when x=1: 2^n = sum [C(n,k)]; k=0,n // 3

    derivatives of both sides of (1+x)^n = sum [C(n,k)*x^k]; k=0,n:
    n(1+x)^(n-1) = sum [k * C(n,k) * x^(k-1)]; k=0,n // 4
    in // 4, when x=1: n*2^(n-1) = sum [k * C(n,k)]; k=0,n // 5

    3. The attempt at a solution
    from // 5, i'll have
    sum [C(2n,k)] = 2^(2n); k=0,2n

    then i tried to divide this by 2:
    sum [C(2n,k)] = 2^(2n)/2 = 2^(2n-1); k=0,n

    but then i realized this can't be correct because there are
    n+1 numbers in the range 0-n,
    2n+1 numbers in the range 0-2n
    so i can't really divide 2n+1 by two and get n+1
     
  2. jcsd
  3. Jan 7, 2017 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Hint: C(2n,n+k) = C(2n,n-k) and (n+k) = 2n - (n-k), so you can relate sum_{k=n..2n} k C(2n,k) = sum_{k=1..n} (n+k)C(2n,n+k) to sum_{k=1..n} k C(2n,k).
     
  4. Jan 7, 2017 #3
    sum_{k=0..2n} k C(2n,k) = n*2^(2n)
    if it was sum_{k=1..2n} k C(2n,k) = n*2^(2n), i'd just divide both sides by 2 and prove the equation
     
  5. Jan 7, 2017 #4

    lurflurf

    User Avatar
    Homework Helper

    ^it is
    $$\sum_{k=0}^n k\,\mathrm{C}(2n,k)=\sum_{k=1}^n k\,\mathrm{C}(2n,k)$$
     
  6. Jan 8, 2017 #5
    yes...

    but i don't understand why these are equal:
    sum_{k=n..2n} k C(2n,k) = sum_{k=1..n} (n+k)C(2n,n+k)
     
  7. Jan 8, 2017 #6

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Who says they are equal?
     
  8. Jan 8, 2017 #7
    the 1st reply?
     
  9. Jan 8, 2017 #8

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    No, absolutely not. Saying that two things are related is not the same as saying they are equal.
     
  10. Jan 10, 2017 #9
    is this correct?

    sum {k=1,2n} c(2n,k) * x^k = (1+x)^(2n)
    sum {k=1,2n} k * c(2n,k) * x^(k-1) = 2n * (1+x)^(2n-1)
    sum {k=1,2n} c(2n,k) = 2^(2n-1), when x=1
    n * 2^(2n-1) = [sum {k=1,2n} c(2n,k)] / 2 = sum {k=1,n} c(2n,k)
     
  11. Jan 13, 2017 #10
    anyone?
     
  12. Jan 14, 2017 #11

    lurflurf

    User Avatar
    Homework Helper

    ^^only the second is correct though the sum should start at 0 to fit the others
    in all k should start at 0
    in the third and forth even though you had k * c(2n,k) in the second the k disappeared

    sum {k=0,2n} c(2n,k) * x^k = (1+x)^(2n)
    sum {k=0,2n} k * c(2n,k) * x^(k-1) = 2n * (1+x)^(2n-1)
    sum {k=0,2n} k*c(2n,k) = 2^(2n-1), when x=1
    n * 2^(2n-1) = [sum {k=0,2n} k*c(2n,k)] / 2 = sum {k=0,n} k*c(2n,k)
     
  13. Jan 14, 2017 #12
    oh yes, that's true

    but i don't get how these two are equal - [sum {k=0,2n} k*c(2n,k)] / 2 = sum {k=0,n} k*c(2n,k)

    for the left part we have
    c(2n,0)*0 + c(2n,1)*1 + ... + c(2n,n-1)*(n-1) + c(2n,n)*n + c(2n,n+1)*(n+1) + ... + c(2n,2n)*2n

    having c(2n,k) = c(2n,2n-k), by summing all the coefficients of these c(2n,k) = c(2n,2n-k) i'll have that every term's coefficient is 2n, except for c(2n,n)*n.

    after this, i don't think i can divide sum {k=0,2n} k*c(2n,k) by 2 and say it's equal to sum {k=0,n} k*c(2n,k)
     
  14. Jan 14, 2017 #13

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    For ##n=6## the sequence of values ##k \,C(12,k)## for ##k=1 \ldots 12## is
    12, 132, 660, 1980, 3960, 5544, 5544, 3960, 1980, 660, 132, 12 .
    We do, indeed, have ##\sum_{k=1}^6 k\, C(12,k) = \sum_{k=7}^{12} k \,C(12,k)= (1/2)\sum_{k=1}^{12} k\, C(12,k)##.

    However, you need to prove that in general, for any ##n##.
     
    Last edited: Jan 14, 2017
  15. Jan 17, 2017 #14
    but why are there two 5544's? we have only one c(12,6). for others there are equals, for example c(12,8) = c(12,4) etc.
     
  16. Jan 17, 2017 #15

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Do the calculation yourself: (1) compute C(12,k) for k = 1, 2, ..., 12; (2) multiply the entries by k = 1,2,..., 12, to get the sequence k*C(12,k) for k from 1 to 12.

    It seems odd that the C's go up and then down again as k increases, while the entries k themselves continue to go up, but nevertheless their product goes up, then down and in a symmetric way. Until you have seen it happen you might not believe it; that is why a numerical example is helpful.
     
  17. Jan 17, 2017 #16
    okay, i need to prove that sum {k=0,n} k*c(2n,k) = 1/2 * sum {k=0,2n} k*c(n/k)

    for n=3,
    for on left side i have ##\text{0*c(6,0) + 1*c(6,1) + 2*c(6,2) + 3*c(6,3) = 0 + 6 + 15 + 60 = 81}##
    and on the right side ##\text{0*c(6,0) + 1*c(6,1) + 2*c(6,2) + 3*c(6,3) + 4*c(6,4) + 5*c(6,5) + 6*c(6,6)] = 81 + 60 + 30 + 6 = 177}##

    since ##\text{c(n,k) = c(n,n-k)}##, here we can notice that the sum of the coefficients of c(2n,k) and c(2n,2n-k) is 2n but this isn't true for c(2n,n)
    for example, ##\text{c(6,1) = c(6,5)}##, the sum of their coefficients: 1 + 5 = 6 = 2n, the same holds for the others but c(6,3) is unique

    and also ##\frac {177} 2 ≠ 81##
     
  18. Jan 17, 2017 #17

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Of course, ##\sum_{k=0}^n k C(2n,k) = \sum_{k=1}^n k C(2n,k)##, etc., and that is why I wrote the sums starting from 1 instead of 0. You get the required symmetry when you start at 1.

    Beyond that, I don't know what else I can say without solving the problem for you. You need to actually evaluate numerically the terms ##k C(12,k)## to see what you get. But, I would suggest you do another case instead, so maybe look at ##n = 5## and thus look at the sequence ##k C(10,k)## for ##k = 1,2, \ldots, 10##. Do not leave the terms in symbolic form such as ##7 C(10,7)## for example; evaluate them numerically, so that you write ##840## instead of ##7 C(10,7).##
     
  19. Jan 17, 2017 #18
    i calculated the second term wrong, so for n=3 the sequence of terms is
    ##\text{0 6 30 60 60 30 6}##
    so it turns out that ##\text{n*c(2n,n) = (n+1)*c(2n,n+1)}## and i really wonder why and how

    ##\text{(n+1)*c(2n,n+1) = n*c(2n,n+1) + c(2n,n+1)}## but this doesn't get me anywhere
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted