1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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}$$ $\endgroup$ – Kari Apr 3 '15 at 21:41
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Michael Smith Apr 3 '15 at 21:52
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Apr 3 '15 at 22:00
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Michael Smith Apr 3 '15 at 21:56
  • $\begingroup$ 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)$. $\endgroup$ – kryomaxim Apr 3 '15 at 21:58
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Michael Smith Apr 3 '15 at 21:48
  • $\begingroup$ 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$. $\endgroup$ – William Stagner Apr 3 '15 at 21:53
0
$\begingroup$

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

$\endgroup$

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.