................n
Prove that ∑ k*C(n, k) = n2^(n - 1)
.............k = 1
NB:
C(x, y) = x!/[y!(x - y)!]
Use binomial expansion, it will be easier to prove then,
we know that
...................n
(1 + x)^n = ∑ C(n,k) x^k
...............k=0
Now diffrentiate wrt "x"
............................n
n*(1 + x)^(n - 1) = ∑ C(n,k) k x^(k - 1)
.........................k=0
In RHS we can start the summation from 1 instead of 0 since fist term will be zero because of the presence of "k", so, we have
.........................k=1
Now put x = 1 and you will get
......................n
n*(2)^(n - 1) = ∑ k * C(n,k)
...................k=1
Ohh, I've just thought of a really neat trick!
k * C(n, k) = k * n! / [(n - k)! * k!]
= n! / [(n - k)! * (k - 1)!]
= n * (n - 1)! / [(n - k)! * (k - 1)!]
= n * C(n - 1, k - 1)
Let:
S = sum(k = 1, n) [ k * C(n, k) ]
Then:
= sum(k = 1, n) [ n * C(n - 1, k - 1) ]
= n * sum(k = 1, n) [ C(n - 1, k - 1) ]
Now, this sum is easily computable if you know the following formula:
sum(k = 0, n) [ C(n, k) ] = 2^n
This can be seen easily by looking at the binomial expansion for (1 + 1)^n. So we have:
S = n * sum(k = 1, n) [ C(n - 1, k - 1) ]
= n * 2^(n - 1)
as required.
Looks oddly like a proof by induction...
Copyright © 2024 1QUIZZ.COM - All rights reserved.
Answers & Comments
Verified answer
Use binomial expansion, it will be easier to prove then,
we know that
...................n
(1 + x)^n = ∑ C(n,k) x^k
...............k=0
Now diffrentiate wrt "x"
............................n
n*(1 + x)^(n - 1) = ∑ C(n,k) k x^(k - 1)
.........................k=0
In RHS we can start the summation from 1 instead of 0 since fist term will be zero because of the presence of "k", so, we have
............................n
n*(1 + x)^(n - 1) = ∑ C(n,k) k x^(k - 1)
.........................k=1
Now put x = 1 and you will get
......................n
n*(2)^(n - 1) = ∑ k * C(n,k)
...................k=1
Ohh, I've just thought of a really neat trick!
k * C(n, k) = k * n! / [(n - k)! * k!]
= n! / [(n - k)! * (k - 1)!]
= n * (n - 1)! / [(n - k)! * (k - 1)!]
= n * C(n - 1, k - 1)
Let:
S = sum(k = 1, n) [ k * C(n, k) ]
Then:
S = sum(k = 1, n) [ k * C(n, k) ]
= sum(k = 1, n) [ n * C(n - 1, k - 1) ]
= n * sum(k = 1, n) [ C(n - 1, k - 1) ]
Now, this sum is easily computable if you know the following formula:
sum(k = 0, n) [ C(n, k) ] = 2^n
This can be seen easily by looking at the binomial expansion for (1 + 1)^n. So we have:
S = n * sum(k = 1, n) [ C(n - 1, k - 1) ]
= n * 2^(n - 1)
as required.
Looks oddly like a proof by induction...