how to prove: $\sum\limits_{k=1}^n k\binom{n}{k}=n \cdot 2^{n-1} $

Question

need help to prove this: $\sum\limits_{k=1}^n k\binom{n}{k}=n \cdot 2^{n-1} $ where $n$ is integer $\geq 1$.

Question also said taking the derivative of $(1 + x)^n$ would be helpful which I've found to be $n(1+x)^{n-1}$

any help appreciated, thank you.

Answer 1

Using the binomial identity shown in $(3)$, we have $$ \begin{align} k\binom{n}{k} &=\binom{k}{1}\binom{n}{k}\\ &=\binom{n}{1}\binom{n-1}{k-1}\tag{1} \end{align} $$ Now sum $(1)$: $$ \begin{align} \sum_{k=1}^nk\binom{n}{k} &=\sum_{k=1}^n\binom{n}{1}\binom{n-1}{k-1}\\ &=n2^{n-1}\tag{2} \end{align} $$

---

Binomial Identity $$ \begin{align} \binom{n}{k}\binom{k}{j} &=\lower{10pt}\overset{\displaystyle\overbrace{\binom{n-j}{k-j}\frac{n-j+1}{k-j+1}\cdots\frac{n}{k}}^{\binom{n}{k}}\binom{k}{j}}{\hphantom{\binom{n-j}{k-j}}\underbrace{\hphantom{\frac{n-j+1}{k-j+1}\cdots\frac{n}{k}\binom{k}{j}}}_{\binom{n}{j}}}\\ &=\binom{n-j}{k-j}\binom{n}{j}\tag{3} \end{align} $$

Answer 2

$(1+x)^n=\sum\limits_{k=0}^n {n \choose k}x^k$.

Now differentiate both sides with respect to $x$ and put $x=1$.

Answer 3

Let $S = \sum_{k = 1}^n k\binom{n}{k} = \sum_{k = 0}^n k\binom{n}{k}$. Then

$$S = \sum_{k = 0}^n \left[n\binom{n}{k} - (n-k)\binom{n}{k}\right] = \sum_{k = 0}^n \left[n\binom{n}{k} - (n-k)\binom{n}{n-k}\right] = n\sum_{k = 0}^n \binom{n}{k} - S.$$

Solving for $S$, we obtain $$S = \frac{n}{2}\sum_{k = 0}^n \binom{n}{k} = \frac{n}{2}\cdot 2^n = n\cdot 2^{n-1}$$

Answer 4

Creating a story to prove a combinatorial identity by double counting is always fun.

LHS: Choose $k$ among $n$ objects, and then choose one favorite object among the $k$. Here, $k$ should be at least 1, and can be as much as $n$.

RHS: Start by choosing one favorite among the $n$ objects. Then for each of the $n-1$ remaining objects, decide one at a time whether to include it or not.