Proving equality - a sum including binomial coefficient $\sum_{k=1}^{n}k{n \choose k}2^{n-k}=n3^{n-1}$

Question

I want to prove the following equality:

$$\displaystyle\sum_{k=1}^{n}k{n \choose k}2^{n-k}=n3^{n-1}$$

So I had an idea to use $((1+x)^n)'=n(1+x)^{n-1}$

So I could just use the binomial theorem and let $$x=2 \implies (n3^{n-1})$$ and then modify the sum into that one on the left side.

So I need to prove that : $$\displaystyle\sum_{k=1}^{n}k{n \choose k}2^{n-k}=n(1+x)^{n-1}$$ if$$x=2$$ Any help would be appreciated.

Answer 1

From the binomial formula we have:

$(2+x)^n = \sum_{k=0}^{n} {n \choose k} \cdot 2^{n-k} \cdot x^k$

Let's take the derivative on both sides. We get:

$n \cdot (2+x)^{n-1} \cdot 1 = \sum_{k=1}^{n} {n \choose k} \cdot k \cdot 2^{n-k} \cdot x^{k-1}$

(note that the sum now starts with $k=1$ because that term which
had $k=0$ was a constant, and is now gone after taking the derivative).

Now we put $x = 1$ and we're done with the proof.

Answer 2

We can do this using a nice combinatorial proof. Let's say we have $n$ boxes in a row. We want to paint them all yellow, red, and blue, and one special box of choice gold. So we can first choose the special box ($n$ possibilities) and then choose for every leftover box whether we'll paint it yellow, red or blue ($3^{n-1}$ possibilities). This totals $n3^{n-1}$ possibilities.

---

We can also first choose the boxes that'll be yellow-ish (that is, yellow or gold). Let's say we choose $k$ of them to be so (so there's $k-1$ yellow boxes). There's $\binom{n}{k}$ possibilities for that. Then of the $k$ yellowish boxes we need to paint one gold - $k$ possibilities. For the leftover boxes, we need to choose to paint them red or blue ($2^{n-k}$ possibilities) which reaches a total of $k\binom{n}{k}2^{n-k}$ possibilities. To reach all possibilities though, we need to range $k$ from $1$ (since we need a gold box) to $n$ (one box gold and the rest yellow). So this is $\sum_{k=1}^nk\binom{n}{k}2^{n-k}$ possibilities.

---

Thus, $$\sum_{k=1}^nk\binom{n}{k}2^{n-k}=n3^{n-1}$$ as we needed.

Answer 3

We can do it without derivatives using the identity $\color{red}{\binom{n+1}{k+1}={n+1\over k+1}\binom{n}{k}}$, then using the change of variable $\color{blue}{k=r+1}$ and lastly using the binomial theorem. $$\begin{align} S&=\sum_{k=1}^{n}k{n \choose k}2^{n-k}\color{red}=\sum_{k=1}^{n}n{n-1 \choose k-1}2^{n-k}\color{blue}=n\sum_{r=0}^{n-1}{n-1\choose r}2^{(n-1)-r}=n(1+2)^{n-1}=n3^{n-1} \end{align}$$