# Prove the equation using Newton's binom

1. Jan 7, 2017

### Lilia

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. Jan 7, 2017

### Ray Vickson

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).

3. Jan 7, 2017

### Lilia

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

4. Jan 7, 2017

### lurflurf

^it is
$$\sum_{k=0}^n k\,\mathrm{C}(2n,k)=\sum_{k=1}^n k\,\mathrm{C}(2n,k)$$

5. Jan 8, 2017

### Lilia

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)

6. Jan 8, 2017

### Ray Vickson

Who says they are equal?

7. Jan 8, 2017

8. Jan 8, 2017

### Ray Vickson

No, absolutely not. Saying that two things are related is not the same as saying they are equal.

9. Jan 10, 2017

### Lilia

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)

10. Jan 13, 2017

### Lilia

anyone?

11. Jan 14, 2017

### lurflurf

^^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)

12. Jan 14, 2017

### Lilia

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)

13. Jan 14, 2017

### Ray Vickson

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
14. Jan 17, 2017

### Lilia

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.

15. Jan 17, 2017

### Ray Vickson

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.

16. Jan 17, 2017

### Lilia

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$

17. Jan 17, 2017

### Ray Vickson

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).$

18. Jan 17, 2017

### Lilia

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