Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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$).
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.
$$\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
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}$$
