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).
This article has been written by Robin Pourtaud ([email protected]) and published on September 3, 2021.
The content of this article is licensed under CC BY
NC 4.0 : You can freely share and adapt the content for non-commercial purposes as long as you give
appropriate credit and provide a link to the license. In my case, the link to the original article is enough.
Confidentiality if relevant: https://devmath.fr/page/confidentialite/
Identity:
One of the famous formulas using binomial coefficients is:
$$\sum^n_{k=1} k\binom{n}{k} = n \times 2^{n-1}$$
The proof:
- We start by using Newton’s binomial formula:
$$\sum^n_{k=1} \binom{n}{k}a^{k}b^{n-k}=(a+b)^n$$
- Let $b = 1$, then :
$$\sum^n_{k=1} \binom{n}{k}a^{k} = (a+1)^n$$
- Differentiate both members of the equation with respect to $a$ like this:
$$\frac{d}{da}(\sum^n_{k=1} \binom{n}{k}a^{k} = (a+1)^n)$$
- Which gives us:
$$\sum^n_{k=1} \binom{n}{k}ka^{k-1} = n(a+1)^{n-1}$$
- We can now take $a = 1$ and get:
$$\sum^n_{k=1} k\binom{n}{k} = n \times 2^{n-1}$$