Prove $\sum_{k= 0}^{n} k \binom{n}{k} = n \cdot 2^{n - 1}$ using the binomial theorem

Solution 1:

You can avoid calculus altogether by first using the identity $k\binom{n}k=n\binom{n-1}{k-1}$:

$$\begin{align*} \sum_{k=0}^nk\binom{n}k&=\sum_{k=1}^nk\binom{n}k\\ &=\sum_{k=1}^nn\binom{n-1}{k-1}\\ &=n\sum_{k=0}^{n-1}\binom{n-1}k\\ &=n\sum_{k=0}^{n-1}\binom{n-1}k1^k1^{n-k}\\ &=n(1+1)^{n-1}\\ &=n2^{n-1} \end{align*}$$

Added: I prefer a combinatorial proof, but that doesn’t use the binomial theorem. For completeness I’ll include one, though I’m pretty sure that I’ve posted one before. You have a pool of $n$ players, and you want to choose a team of one or more players, one of whom you will designate as captain. If you choose a team of $k$ players, there are $\binom{n}k$ ways to pick the team, and then there are $k$ ways to pick the captain, so there are $k\binom{n}k$ captained teams of $k$ players; summing over $k$ gives the total number of captained teams. On the other hand, you can pick the captain first (in $n$ different ways) and then pick any subset of the remaining $n-1$ players to fill out the team. Since there are $2^{n-1}$ subsets of any set of $n-1$ things, there are altogether $n2^{n-1}$ ways to pick a captained team.

Solution 2:

Start from: $$(1+x)^n = \sum_{k=0}^{n}\binom{n}{k}x^k \tag{1} $$ differentiate both sides with respect to $x$: $$ n(1+x)^{n-1} = \sum_{k=1}^{n}\binom{n}{k}k x^{k-1}\tag{2}$$ then evaluate at $x=1$. As an equivalent alternative, notice that: $$ k\binom{n}{k} = n\binom{n-1}{k}.\tag{3}$$