Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

6 Answers 6

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.

share|improve this answer
add comment

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

share|improve this answer
    
In the last line, at the second equals. Instead of $$\sum_{k=2}^{\infty}$$ would be? $$\sum_{k=1}^{\infty}$$ –  Italo Brenner Jun 26 at 12:41
add comment

Hint: Taylor expand $$\left(x\frac{d}{dx}-1\right)\frac{1}{1-x}$$ around $x=0$.

share|improve this answer
add comment

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$

share|improve this answer
add comment

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

share|improve this answer
add comment

(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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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