Proof of Binomial Formula Summation - Induction

Question

Let $n\geq 1$ be an integer. Prove that $$ \sum_{k=1}^n k\binom{n}{k} = n\cdot 2^{n-1}. $$

Not sure how to go about doing this question. It says that finding the derivative of $(1+x)^n$ is useful. Any ideas?

Answer 1

$$(1+x)^n = {n \choose 0}x^0 + {n \choose 1}x^1 + {n \choose 2}x^2 + \cdots + {n \choose {n-1}}x^{n-1} + {n \choose n}x^n$$ So, now we're going to differentiate both sides and substitute $x=1$. $$n(1+x)^{n-1}={n \choose 1} + 2{n \choose 2}x + \cdots + (n-1){n \choose {n-1}}x^{n-2} + n{n \choose n}x^{n-1}$$ $$\large \boxed{\sum_{k=1}^n \ k {n \choose k}= n \cdot 2^{n-1}}$$

Answer 2

For another solution, recall that for any $m\geqslant 0$, $\sum_{k=0}^m\binom mk=2^m$ (each side of the equation counts the number of subsets of $\{0,1,\ldots, m\}$). Hence $$ \begin{align*} \sum_{k=1}^n k\binom nk &= \sum_{k=1}^n \frac{kn!}{k!(n-k)!}\\ &= n\sum_{k=1}^n \frac{(n-1)!}{(k-1)!(n-k)!}\\ &= n\sum_{k=0}^{n-1}\frac{(n-1)!}{k!(n-1-k)!}\\ &= n\sum_{k=0}^{n-1}\binom{n-1}k\\ &= n2^{n-1}. \end{align*} $$