# Sum of $k {n \choose k}$ is $n2^{n-1}$

Proof that $\suṃ̣_{k=1}^{n}k {n \choose k}$ for $n \in \mathbb N$ is equal to $n2^{n-1}$.

As a hint I got that $k {n \choose k} = n {n-1\choose k-1}$.

I tried solving this by induction but, in the inductive step I'm not arriving to the correct result.

• Factor out the $n$ using given identity and adjust the remaining sum so that you can use the known sum of binomial coefficients. – Marcin Łoś Feb 20 '14 at 17:05

Just change the index $s=k-1$

$$\sum_{k=1}^{n}k {n \choose k} = n\sum_{k=1}^{n} {n-1\choose k-1}= n\sum_{s=0}^{n-1} {n-1\choose s} =n2^{n-1}$$

One possible proof:

Because $$(1+x)^n = \sum_{k=0}^n {n \choose k} x^k,$$ then by taking derivative, $$n(1+x)^{n-1} = \sum_{k=1}^n k{n \choose k} x^{k-1}.$$ Let $x=1$, we obtain that $$n2^{n-1} = \sum_{k=1}^n k {n \choose k}.$$

\begin{align*} &A = \sum_{k\geq1}^{n}k\cdot \binom{n}{k} \\ \end{align*}

$A$ is the no of ways to form a committee of $k \geq 1$ people out of $n$ available individuals and select one head for the selected committee.

Empty committee is not possible. Therefore we select the head first in $n$ ways and then any subset out of $(n-1)$ remaining people in $2^{n-1}$ ways.

\begin{align*} &A =n\cdot2^{n-1} \\ \end{align*}

Another way to do this is to differentiate the identity $$(1 + x)^n = \sum_{k=0}^n \binom{n}{k}x^k$$ and then put $x = 1$.