4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is a side point but would it right to say that summations like these cannot be solved by telescoping? $\endgroup$ – hypergeometric Feb 15 '16 at 14:37
6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ so basically there are at least 4 ways to solve it already. $\endgroup$ – MathIsTheWayOfLife Feb 15 '16 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.