1

In a Udacity course I'm told the following: $\sum_{i=1}^{\log_2 (P)} 1/2^i = (P-1) /P $

I've checked that it's true by entering it into Wolfram Alpha: https://www.wolframalpha.com/input/?i=sum+1%2F2^n,+n%3D1+to+log%282,P%29

Could someone help me understand how the $ (P-1)/ P $ result is derived?

Nikunj
  • 6,160
Avatar33
  • 145
  • You can easily show that for any positive integer $n$ we have $\sum_{i=1}^n\frac{1}{2^i}=1-\frac{1}{2^n}$. Now put $n=\log_2P$. – almagest May 04 '16 at 14:18
  • 1
    Hint: Use the https://en.wikipedia.org/wiki/Geometric_series and the fact that $2^{\log_2P}=P$ – gammatester May 04 '16 at 14:18
  • 1
    Note: you should edit the question header to match the actual question. – lulu May 04 '16 at 14:23

4 Answers4

1

In general $$S(k) = \sum_{i=1}^k \frac 1{2^i}\implies \frac 12 S(k)=S(k)-\frac 12 +\frac 1{2^{k+1}}\implies S(k)=1-\frac 1{2^{k}}$$

It follows that your sum is $$S(\log_2(P))=1-\frac 1{2^{\log_2 P}}=1-\frac 1P=\frac {P-1}{P}$$

(of course this is only valid when $\log_2 P\in \mathbb N$. For general $P$ you have to round down to the nearest power of $2$.)

lulu
  • 70,402
1

Notice that this is a geometric progression with number of terms =$\log_2 P$

The sum of such a sequence is given by :

$$\frac{\frac{1}{2}(1-(\frac{1}{2})^{\log_2 P})}{1-\frac{1}{2}}$$ $$=1-\frac{1}{P}$$ $$=\frac{P-1}{P}$$

Nikunj
  • 6,160
  • Thanks. Once I'd seen the general formula from the wiki page above, this answer was simplest to understand. – Avatar33 May 04 '16 at 15:13
0

It is obtained by putting all terms on $2^{log(P)} $:

$ \sum_{i=1}^{log(P)} \frac{1}{2^i} = \frac{\sum_{i=1}^{log(P)} 2^{log(P)-i} }{2^{log(P)}} = \frac{\sum_{i=0}^{log(P)-1} 2^{i} }{P} = \frac{P-1}{P} $

Vincent
  • 2,318
0

$ I(k) = \frac 12 + \frac 14 + \dots + \frac {1}{2^{k}}.$

$\Rightarrow 2 I(k) = 1+ \frac 24 + \dots + \frac{2}{2^k} = 1+ ( \frac 12 + \dots + \frac {1}{2^{k-1}})=1+ (I(k) - \frac {1}{2^k})$

$\Rightarrow I(k) = 1-\frac{1}{2^k}$

Suppose that $k$ is chosen so that $2^k = P$ (here $P$ is a power of two), that is $k=\log_2(P)$.

Then $I(k) = 1- 1/P = \frac{P-1}{P}$.

Can you recover a similar formula for $\frac 1m+ \frac 1{m^2} + \dots + \frac{1}{m^k}$ ? ($m$ positive real number)

Fnacool
  • 7,519