How to derive $\sum_{k=0}^{n}2^{k}(n-k) = 2^{n+1} - n - 2$? In answering this question, I thought about working out a closed-form formula for $f(n)$ there. I got as far as writing:
$$ f(n) = \sum_{k=0}^{n}2^{k}(n-k) $$
…but I wasn't sure how to go farther. I plugged this into Wolfram Alpha and it spat out this:
$$\sum_{k=0}^{n}2^{k}(n-k) = 2^{n+1} - n - 2$$
I've been staring at this for a while but I don't see how to derive the right-hand side from the left-hand side. Would someone be willing to clarify this for me?
 A: Rewrite it as $n\sum_{k=0}^n2^k-\sum_{k=0}^nk2^k$; the first summation is just a geometric series, and the second has been treated here quite a few times. Here’s one of many ways to deal with it:
$$\begin{align*}
\sum_{k=1}^nk2^k&=\sum_{k=1}^n\sum_{\ell=1}^k2^k\\
&=\sum_{\ell=1}^n\sum_{k=\ell}^n2^k\\
&=\sum_{\ell=1}^n\left(\left(2^{n+1}-1\right)-\left(2^{\ell}-1\right)\right)\\
&=\sum_{\ell=1}^n\left(2^{n+1}-2^\ell\right)\\
&=n2^{n+1}-\sum_{\ell=1}^n2^\ell\\
&=n2^{n+1}-\left(2^{n+1}-1\right)\\
&=(n-1)2^{n+1}+1\;.
\end{align*}$$
A: Consider a row of $n+1$ light switches. The number of ways to toggle these switches so that at least $2$ are turned on is $2^{n+1} - \binom{n+1}{1} - \binom{n+1}{0} = 2^{n+1}-n-2$.
Now, suppose we paint red the second to last light switch turned on (going left to right). Then if the $k+1$st switch is toggled, the number of choices for the other switches is $2^k(n-k)$, since we have no restrictions on the $k$ switches to the left, while exactly one of the switches to the right of the red switch must be turned on.
We can have $0 \leq k \leq n$, so $\sum_{k=0}^n 2^k(n-k) = 2^{n+1}-n-2$, as desired.
A: Hint: $k2^k = \lim_{p \mapsto ln(2)}\frac{de^{p k}}{dp} = \lim_{p \mapsto ln(2)}ke^{pk}$.
Use the linearity of the sum (and interchangability of $\frac{d}{dp}$ and summation) and use geometric series.
A: First, look at $\sum_{k=0}^n x^k = \frac{1-x^{n+1}}{1-x}$. If you differentiate this, you get $\sum_{k=0}^n k x^{k-1} = \frac{d}{dx}[\frac{1-x^{n+1}}{1-x}]$, so $\sum_{k=0}^n k x^k = x \sum_{k=0}^n k x^{k-1} = x \frac{d}{dx}[\frac{1-x^{n+1}}{1-x}]$.
Now, $\sum_{k=0}^n n 2^k = n \sum_{k=0}^n 2^k$ which you can calculate out with the afformentioned fact $\sum_{k=0}^n x^k = \frac{1-x^{n+1}}{1-x}$. 
The remaining term can be calculated with $\sum_{k=0}^n k x^k=  x \frac{d}{dx}[\frac{1-x^{n+1}}{1-x}]$ by taking $x=2$.
A: Induction on $n$ will get you the second equality. In the base case, $n=0$, and the equality can be seen. Now assume that for some $n$ we have 
$$
\sum_{k=0}^n2^k(n-k)=2^{n+1}-n-2.
$$
Now consider 
$$
\sum_{k=0}^{n+1}2^k(n+1-k).
$$
Distribute $2^k$ to get 
$$
\sum_{k=0}^{n+1}2^k(n+1-k)=\sum_{k=0}^{n+1}(2^k(n-k)+2^k)=\sum_{k=0}^{n+1}2^k(n-k)+\sum_{k=0}^{n+1}2^k.
$$
Now peel off the last term in the first sum and simplify the second sum to get
$$
\sum_{k=0}^{n+1}2^k(n-k)+\sum_{k=0}^{n+1}2^k=\sum_{k=0}^n2^k(n-k)-2^{n+1}+2^{n+2}-1.
$$
Finally, apply the induction hypothesis to get 
$$
\sum_{k=0}^n2^k(n-k)-2^{n+1}+2^{n+2}-1=2^{n+1}-n-2-2^{n+1}+2^{n+2}-1,
$$
and simplifying gives 
$$
\sum_{k=0}^{n+1}2^k(n+1-k)=2^{n+2}-(n+1)-2.
$$
Therefore the equality will hold for all $n$ by induction. 
A: You can prove this by induction:
\begin{eqnarray}
\sum_{k=0}^{n+1}2^k(n+1-k) &=& \sum_{k=0}^{n+1}2^k(n - k) + \sum_{k=0}^{n+1}2^k \\
&=& (2^{n+1} - n - 2) - 2^{n+1} + (2^{n+2}-1) \\
&=& 2^{n+2} - (n+1) - 2.
\end{eqnarray}
A: Let 
$$\begin{align}
G&=\sum_{k=0}^n 2^k=2^{n+1}-1\\
A&=\sum_{k=0}^n k2^k\\
\Rightarrow 2A&=\sum_{k=0}^n k2^{k+1}=\sum_{k=1}^{n+1}(k-1)2^k\\
\Rightarrow 2A-A&=n2^{n+1}-\sum_{k=1}^{n}2^k\\
\Rightarrow A&=n2^{n+1}-G+1=n2^{n+1}-2^{n+1}+2\\
&=(n-1)2^{n+1}+2\\
\end{align}$$
Hence
$$\begin{align}
\sum_{k=0}^{n}2^k(n-k)
&=n\sum_{k=0}^n2^k-\sum_{k=0}^nk2^k\\
&=nG-A\\
&=n(2^{n+1}-1)-[(n-1)2^{n+1}+2]\\
&=2^{n+1}-n-2\qquad\blacksquare 
&\end{align}$$
