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

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