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?
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*}$$
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.
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}
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}$$
