How can I show that $\sum_{k=0}^{\infty} \frac{k-1}{2^k} = 0$? I'm studying the algorithms book and I have a doubt.
I don't know how can I prove this summation:
$$\sum_{k=0}^{\infty} \frac{(k-1)}{2^k} = 0$$
 A: Hint
Consider $$\sum_{k=0}^{\infty} (k-1){x^k} =\sum_{k=0}^{\infty} k{x^k}-\sum_{k=0}^{\infty} {x^k}=x\sum_{k=0}^{\infty} k{x^{k-1}}-\sum_{k=0}^{\infty} {x^k}$$ and notice that the first sum is the derivative of $something$. So, you face a geometric series and more or less its derivative. Use the formulas and replace $x$ by $\frac{1}{2}$.
I am sure that you can take from here.
A: We have for $|x|<1$
$$\sum_{k=1}^\infty x^k=\frac{x}{1-x}$$
so we differentiate term by term:
$$\sum_{k=1}^\infty k x^{k-1}=\frac{d}{dx}\frac{x}{1-x}=\frac{1}{(1-x)^2}$$
Now we write the given sum in this form (with $x=\frac12$)
$$\sum_{k=0}^\infty\frac{k-1}{2^k}=-1+\sum_{k=2}^\infty\frac{k-1}{2^k}=-1+\frac14\sum_{k=1}^\infty\frac{k}{2^{k-1}}=-1+\frac14\times\frac{1}{\left(1-\frac12\right)^2}=0$$
A: Let $S = \sum_{k=0}^{\infty}\frac{k-1}{2^k}$.
Then $2S = \sum_{k=0}^{\infty}\frac{k-1}{2^{k-1}} = \sum_{k=-1}^{\infty}\frac{k}{2^{k}}$. 
Subtract first equation from second one.
$S = -2 + \sum_{k=0}^{\infty}\frac{1}{2^k} = -2 + 2 = 0$
A: Hint: Taylor expand
$$\left(x\frac{d}{dx}-1\right)\frac{1}{1-x}$$
around $x=0$.
A: Define
$$f(x)=\sum_{k=2}^\infty x^{k-1}=\frac x{1-x}$$
for $x\in(0,1)$.
Then,
$$f'(x)=\sum_{k=2}^\infty(k-1)x^{k-2}=\frac{1}{(1-x)^2}$$
Therefore,
$$\sum_{k=0}^\infty\frac{k-1}{2^k}=-1+0+\frac14f'(\frac12)=-1+\frac44=0$$
A: (The first term is negative and the second term is zero. So not all terms are positive.) 
Rewrite the sum as $$ \lim_{ n \to \infty} \sum_{k = 1}^{k = n } \frac {k -2}{2^{k-1}} $$.
This is an arithmetico geometric series. 
For a general arithmetico geometric series with the first term a,  difference d and common ratio r we have :
$$ \sum _{k = 1}^{k = n }  \left [ a + (k-1) d \right ]r^{k-1} = \frac {a - [ a + (n-1)d] r^{n}}{1-r} + \frac {dr( 1- r^{n-1})}{(1-r)^2} $$
Thus, the sum in the present case is  given as  :
$$ \lim_{ n \to \infty } \left [  \displaystyle \frac {-1 - [n-2]   \displaystyle \frac {1}{2^{n}}}{ \displaystyle  \frac {1}{2}}  + 2 \left ( 1 - \displaystyle \frac {1}{2^{n-1}} \right ) \right ]$$
Thus the sum is 0.
