Possible Duplicate:
How to compute the formula $\sum \limits_{r=1}^d r \cdot 2^r$?

How can I calculate precise value of that series: $\sum\limits_{i=0}^{n-1} i2^i$ ?

So far, I tried to differentiate the $ \sum\limits_{i=0}^{n} 2^i = 2^{i-1} - 1 $ series, but by result $2^n(n+2)$ isn't correct according to Wolfram ($2^n (n-2)+2$).


marked as duplicate by Martin Sleziak, Asaf Karagila, Chris Eagle, Thomas, draks ... Dec 4 '12 at 20:40

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ One method: multiply series by 2 so the same coefficient shifts to a higher power, then subtract the two series and then simplify. $\endgroup$ – Frenzy Li Dec 4 '12 at 15:36
  • $\begingroup$ I feel like this is an exact duplicate of another question (probably several others) but can't find the dupe offhand... $\endgroup$ – Steven Stadnicki Dec 4 '12 at 15:46
  • $\begingroup$ You may want to use $k$ instead of $i$ so it is clear you aren't talking about $\sqrt{-1}$... :) (You had me confused for a bit...) $\endgroup$ – apnorton Dec 4 '12 at 15:48
  • $\begingroup$ @anorton - okay, I'll remember about that in the future. It's part of algorithmic exercise, so $i$ stands for iterator, like in C++. $\endgroup$ – Greg Witczak Dec 4 '12 at 15:54

$$\begin{array}{rll} S &=1\cdot2^1+&2\cdot2^2+3\cdot2^3+\cdots+(n-2)\cdot2^{n-2}+(n-1)\cdot2^{n-1} \\ 2S &= &1\cdot2^2+2\cdot2^3+\cdots+(n-3)\cdot2^{n-2}+(n-2)\cdot2^{n-1}+(n-1)\cdot2^{n} \end{array}$$



So, $S=2+2^n(n-2)$

Refernce: Arithmetico-geometric series

  • $\begingroup$ Did I miss something, or you forgot about $-2^n$ from $(n-1)*2^n$ multiplication? $\endgroup$ – Greg Witczak Dec 4 '12 at 15:51
  • $\begingroup$ @gogowitczak, $2(2^n-1)-n2^n=-2-2^n(n-2)$, right? $\endgroup$ – lab bhattacharjee Dec 4 '12 at 15:53
  • $\begingroup$ I still think that there is a small mistake in your calculations (I have $(2^1 + 2^2 + ... + 2^{n-1} + 2^n) - n*2^n$), but the final answer is the same. Thanks a lot for your efford! $\endgroup$ – Greg Witczak Dec 4 '12 at 16:03
  • $\begingroup$ $ 2^1 + 2^2 + ... + 2^n = \sum\limits_{i=1}^{n}(2^i) = \sum\limits_{i=0}^{n}(2^i) - 1 = (2^{n+1} -1) - 1 = 2^{n+1}-2$. And after putting this into final formula, I have $S-2S = 2^{n+1}-2 - n2^n$, so finally $ S = n2^n - 2^{n+1} + 2 = 2^n(n-2) + 2$ $\endgroup$ – Greg Witczak Dec 4 '12 at 16:25
  • $\begingroup$ @gogowitczak, thanks a lot for your observation. Please find the rectifed post. sorry I wrongly deleted my last post. $\endgroup$ – lab bhattacharjee Dec 4 '12 at 16:38

Discrete Calculus works here. Via Discrete Calculus, we have summation by parts:

$$\sum_{m\le k \le n} f_{k}(g_{k+1}-g_k)=f_{n+1}g_{n+1}-f_mg_m-\sum_{m \le k \le n}g_{k+1}(f_{k+1}-f_k), $$ where $f_k$ and $g_k$ are sequences. Let $f_k=k$ and $2^k=g_{k+1}-g_k$. Via observation, we see that $g_k=2^{k}$ since $2^{k+1}-2^k=2^k(2-1)=2^k$. Thus, we have (with $m=0$ and $n=u-1$): $$\sum_{0 \le k \le u-1}k2^k=u2^u-0\cdot 2^0-\sum_{0 \le k \le u-1}2^{k+1}(k+1-k)=u2^u-\sum_{0 \le k \le u-1}2^{k+1}.$$

From here it can be solved by noting the second sum is geometric! :-)

A more beautiful formulation of summation by parts possesses the forward difference operator defined $\Delta f_k=f_{k+1}-f_k$. In essence, it's a substitution:

$$\sum_{m \le k \le n}f_k\Delta g_k=f_{n+1}g_{n+1}-f_mg_m-\sum_{m \le k \le n}g_{k+1}\Delta f_k.$$

The reason it is called 'summation by parts' is because of the fact it is the Discrete Calculus analog of Continuous Calculus's integration by parts:

$$\int f'gdx=fg-\int fg'dx.$$

Finding the closed form of partial sums is the Discrete Calculus analogy of finding the closed form of indefinite integrals. For a table of the closed form of partial sums and a great elucidation of Discrete Calculus, see Donald E. Knuth's Concrete Mathematics. While a very CS based book and CS is not my thing, I still find it quite enjoyable and educational.

  • 3
    $\begingroup$ I like discrete calculus. It's so much fun. $\endgroup$ – Frenzy Li Dec 4 '12 at 15:59
  • 2
    $\begingroup$ @FrenzYDT, me too! I learned how to apply it via Knuth's beautiful Concrete Mathematics. :) $\endgroup$ – 000 Dec 4 '12 at 16:36
  • 1
    $\begingroup$ Actually I just learnt the super abbreviated paper by David Gleich. I'm ready for more o them. $\endgroup$ – Frenzy Li Dec 4 '12 at 16:41
  • $\begingroup$ Wow! Thank you for the beautifully abbreviated paper, @FrenzYDT.! $\endgroup$ – 000 Dec 4 '12 at 16:46
  • 1
    $\begingroup$ Well, what do I have to say? The community bestowed it upon me (in an answer few weeks ago). I wanna redirect the thanks to the community. Learn knowledge and pass them on. $\endgroup$ – Frenzy Li Dec 4 '12 at 16:49

Using the Geometric Series $$ \sum_{m = 0}^{n-1} r^n = \frac{1-r^n}{1-r} $$ we have that $$ \sum_{m = 1}^{n-1} m 2^{m-1} = \frac{d}{dr}\frac{1-r^n}{1-r}\Big|_{r=2} = 1-2^n + n2^{n-1} $$ but $$ \sum_{m = 1}^{n-1} m 2^{m-1} = \sum_{m = 0}^{n-1} m 2^{m-1} $$ hence $$ \sum_{m = 0}^{n-1} m 2^m = 2(1-2^n + n2^{n-1}) $$


$$x+x^2+x^3+...+x^{n-1}+x^n=\frac {x^{n+1}-x}{x-1}$$ $+$ $$0x+x^2+x^3+...+x^{n-1}+x^n=\frac {x^{n+1}-x^2}{x-1}$$ $+$ $$0x+0x^2+x^3+...+x^{n-1}+x^n=\frac {x^{n+1}-x^3}{x-1}$$ $$.$$ $$.$$ $$.$$ $+$ $$0x+0x^2+0x^3+...+0x^{n-1}+x^n=\frac {x^{n+1}-x^n}{x-1}$$

After adding we get: $$x+2x^2+...+nx^n=\sum_{i=1}^{n}\frac {x^{n+1}-x^i}{x-1}=\frac{nx^{n+1}}{x-1}-\sum_{i=1}^{n}\frac {x^i}{x-1}=\frac{nx^{n+1}}{x-1}-\frac {x^{n+1}-x}{(x-1)^2}$$


Here is another way to do this

Consider the polynomial $$\begin{align}&P(x)=\sum^{n-1}_{i=0} \ i\ \cdot \ x^i= 0x^0 +1x^1+2x^2+3x^3+\cdots +(n-1)\ x^{n-1}\\&Q(x)=\cfrac{P(x)}{x}=1x^0+2x^1+3x^2+\cdots+(n-1)\ x^{n-2}, \quad \quad x \ne 0\\ &\int Q(x)\ \text d x = cx^0+x^1+x^2+x^3+\cdots+ x^{n-1}=c+\sum^{n-1}_{i=1}x^i \\ &\text{by geometric series, we have} \int Q(x)\ \text d x =c+\cfrac{x(1-x^{n-1})}{1-x}\\ &\text{we then differentiate back to have } Q(x)= \cfrac{(n-1) x^{n+1}-n x^n+x}{x(x-1)^2 }\\ &\text{and at last } P(x)=x\cdot Q(x) =\cfrac{(n-1) x^{n+1}-n x^n+x}{(x-1)^2 }\\ &\text{we compute $P(2)$ to get the desired result }\\ &P(2)=\cfrac{(n-1) 2^{n+1}-n\cdot 2^n+2}{(2-1)^2 }=(n-1) 2^{n+1}-n\cdot 2^n+2\ \ =\ \ 2^n(2(n-1)-n)+2\\ &\sum\limits_{i=0}^{n-1} i\cdot 2^i=P(2)=2^n(n-2) +2 \end{align}$$

  • 1
    $\begingroup$ @DejanGovc oui! c'est vrai ça! thank you! $\endgroup$ – user31280 Dec 6 '12 at 2:40

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