Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question


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|cite|improve this answer

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


share|cite|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 '14 at 12:41

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

share|cite|improve this answer

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|cite|improve this answer

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|cite|improve this answer

(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|cite|improve this answer

Your Answer


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.