Calculate the sum of series $\sum\limits_{i=0}^{n-1} i2^i$ [duplicate]

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

One method: multiply series by 2 so the same coefficient shifts to a higher power, then subtract the two series and then simplify. –  FrenzY DT. Dec 4 '12 at 15:36
I feel like this is an exact duplicate of another question (probably several others) but can't find the dupe offhand... –  Steven Stadnicki Dec 4 '12 at 15:46
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...) –  apnorton Dec 4 '12 at 15:48
@anorton - okay, I'll remember about that in the future. It's part of algorithmic exercise, so $i$ stands for iterator, like in C++. –  gogowitczak 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}$$

Subtracting,

$$S-2S=1\cdot2^1+(2-1)\cdot2^2+\cdots+\{(n-2)-(n-3)\}\cdot2^{n-2}+\{(n-1)-(n-2)\}\cdot2^{n-1}-(n-1)2^n=(2^1+2^2+\cdots+2^{n-1})-(n-1)2^n=2\left(\frac{2^{n-1}-1}{2-1}\right)-(n-1)2^n=2^n\{1-(n-1)\}-2$$

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

Refernce: Arithmetico-geometric series

-
Did I miss something, or you forgot about $-2^n$ from $(n-1)*2^n$ multiplication? –  gogowitczak Dec 4 '12 at 15:51
@gogowitczak, $2(2^n-1)-n2^n=-2-2^n(n-2)$, right? –  lab bhattacharjee Dec 4 '12 at 15:53
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! –  gogowitczak Dec 4 '12 at 16:03
$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$ –  gogowitczak Dec 4 '12 at 16:25
@gogowitczak, thanks a lot for your observation. Please find the rectifed post. sorry I wrongly deleted my last post. –  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.

-
I like discrete calculus. It's so much fun. –  FrenzY DT. Dec 4 '12 at 15:59
@FrenzYDT, me too! I learned how to apply it via Knuth's beautiful Concrete Mathematics. :) –  000 Dec 4 '12 at 16:36
Actually I just learnt the super abbreviated paper by David Gleich. I'm ready for more o them. –  FrenzY DT. Dec 4 '12 at 16:41
Wow! Thank you for the beautifully abbreviated paper, @FrenzYDT.! –  000 Dec 4 '12 at 16:46
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. –  FrenzY DT. 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}

-
@DejanGovc oui! c'est vrai ça! thank you! –  user31280 Dec 6 '12 at 2:40