# 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?

• This is an awesome question! Considering the geometric series below and interchanging derivatives and summations might be a good place to start! $$\sum_{k=0}^{n} x^{k}$$ – Kari Apr 3 '15 at 21:41

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

• Thanks! Follow-up query for you, if you're up for it: What pattern of thinking were you using here that let you see this? Was it just that you could see how to simplify this to a computation you happened to know, or is there a kind of way of thinking about these sorts of sums that you're using here? (E.g., in calculus there's a general trick of working out rough approximations of what you want to know and then finding a way to make your error vanishingly small. But I don't see the analog here, if there is one.) – Michael Smith Apr 3 '15 at 21:52
• @Michael: You're welcome. Splitting the difference into two summations was a fairly automatic thought, and at that point I had known expressions. The only other more or less routine possibility was to consider the substitution $\ell=n-k$, which would simplify the $n-k$ factor, but in this case it doesn't really help. – Brian M. Scott Apr 3 '15 at 22:00

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.

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.

• Huh. I think this way of thinking is foreign to me. What inspires you to think of rewriting $k2^k = \lim_{p\rightarrow\ln 2}\frac{de^{pk}}{dp}$? I don't grasp the intuition there. – Michael Smith Apr 3 '15 at 21:56
• This trick is used often. Since $2=e^{ln(2)}$ it can be written $2^k=e^{ln(2)k}$. Now set $p=ln(2)$ as a new variable. Deriving by $p$ you get $ke^{pk}$. Now resubstitute $p=ln(2)$. – kryomaxim Apr 3 '15 at 21:58

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

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.

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}

• Well, sure. I agree that the formula is correct, but what was befuddling me was how I would have worked out the formula in the first place without using Wolfram Alpha. Although I do appreciate you pointing this out; I didn't think to prove that the formula was fully correct, and this is a nice demonstration of how to go about thinking about that. – Michael Smith Apr 3 '15 at 21:48
• Sure! I guess the moral is that the induction argument should contain some intuition, namely that the difference between the $n$th and $(n+1)$th sums is $2^{n+2} - 2^{n+1} - 1$. You can observe some telescoping going on with the $2^k$ terms and the constant term should build up over time, giving you something of the form $2^k - n + c$. – William Stagner Apr 3 '15 at 21:53

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}