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)!]

3 Answers

Relevance
  • Sid
    Lv 6
    1 decade ago
    Favorite 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

  • 1 decade ago

    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.

  • 1 decade ago

    Looks oddly like a proof by induction...

Still have questions? Get your answers by asking now.