5
$\begingroup$

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

  • 0
    @anorton - okay, I'll remember about that in the future. It's part of algorithmic exercise, so $i$ stands for iterator, like in C++.2012-12-04

5 Answers 5

1

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
    @DejanGovc oui! c'est vrai ça! thank you!2012-12-06
11

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.

  • 1
    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.2012-12-04
9

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

  • 0
    @gogowitczak, thanks a lot for your observation. Please find the rectifed post. sorry I wrongly deleted my last post.2012-12-04
7

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

3

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