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

Question

I'm trying to prove that

\begin{equation} \sum_{k= 0}^{n} k \binom{n}{k} = n \cdot 2^{n - 1} \end{equation}

with the Binomial Theorem.

I know that the B.T. states that

\begin{equation} (x + y)^n = \sum_{k= 0}^{n} \binom{n}{k} x^{n-k}y^{k} \end{equation}

The proof that I have tried starts with:

\begin{equation} n \cdot 2^{n-1} = \end{equation}

Actually I am stucked with this step.

Answer 1

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}$$

Answer 2

Hint: set $x=1$, so that both sides are functions only of $y$, and see what happens when you differentiate with respect to $y$.

Answer 3

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.

Answer 4

Since $(1+x)^n=\sum_{k=0}^n \binom{n}{k}x^k$, take the dervative both side, we have $n(1+x)^{n-1}=\sum_{k=1}^n k\binom{n}{k}x^{k-1}$. Now, let $x=1$, we have $n\cdot 2^{n-1}=\sum_{k=1}^n k\binom{n}{k}$.