# Prove that ∑k*C(n, k) = n2^(n - 1)?

................n

Prove that ∑ k*C(n, k) = n2^(n - 1)

.............k = 1

NB:

C(x, y) = x!/[y!(x - y)!]

Relevance
• Sid
Lv 6

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