RPRobin PourtaudTokyo · near the water
Return to the current
Mathematics1 min read

Proof : Sum of k(n choose k)

This article presents the proof of: the sum of k times n choose k = n times 2 to the power of (n minus 1).

ENFR

Identity:

One of the famous formulas using binomial coefficients is:

∑k=1nk(nk)=n×2n−1\sum^n_{k=1} k\binom{n}{k} = n \times 2^{n-1}

The proof:

  1. We start by using Newton’s binomial formula:

∑k=0n(nk)akbn−k=(a+b)n\sum^n_{k=0} \binom{n}{k}a^{k}b^{n-k}=(a+b)^n

  1. Let b=1b = 1, then :

∑k=0n(nk)ak=(a+1)n\sum^n_{k=0} \binom{n}{k}a^{k} = (a+1)^n

  1. Differentiate both members of the equation with respect to aa like this:

dda(∑k=0n(nk)ak)=dda(a+1)n\frac{d}{da}\left(\sum^n_{k=0} \binom{n}{k}a^{k}\right) = \frac{d}{da}(a+1)^n

  1. Which gives us:

∑k=1n(nk)kak−1=n(a+1)n−1\sum^n_{k=1} \binom{n}{k}ka^{k-1} = n(a+1)^{n-1}

  1. We can now take a=1a = 1 and get:

∑k=1nk(nk)=n×2n−1\sum^n_{k=1} k\binom{n}{k} = n \times 2^{n-1}

Others identities here: