# How can I show using mathematical induction that $\frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{2^n} = \frac{2^n - 1}{2^n}$

How can I show using mathematical induction that $\frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{2^n} = \frac{2^n - 1}{2^n}$

Edit: I'm specifically stuck on showing that $\frac{2^n - 1}{2^n} + \frac{1}{2^{n+1}} = \frac{2^{n+1}-1}{2^{n+1}}$.

What should the approach be here?

-
The "approach" is apparently supposed to be induction. What is it you are having trouble with in the induction argument? –  Arturo Magidin May 4 '12 at 20:49
Once I have $\frac{2^n - 1}{2^n} + \frac{1}{2^{n+1}}$, I don't know how to show its equality to $\frac{2^{n+1}-1}{2^{n+1}}$. I've updated the answer to reflect this. –  mirai May 4 '12 at 20:53
Multiply by $\frac{2}{2}$ to get a common denominator, then add. –  AMPerrine May 4 '12 at 20:55
@mirai: Ah; that's not "logic", it's algebra/arithmetic. $$\frac{2^n-1}{2^n}+\frac{1}{2^{n+1}} = \frac{2(2^n-1)}{2(2^n)}+\frac{1}{2^{n+1}} = \frac{2^{n+1}-2}{2^{n+1}}+\frac{1}{2^{n+1}} = \frac{2^{n+1}-2+1}{2^{n+1}} = \frac{2^{n+1}-1}{2^{n+1}}.$$ –  Arturo Magidin May 4 '12 at 20:55

If $T(n) = \frac{1}{2}+\frac{1}{4}+\cdots+\frac{1}{2^n}$, then $$T(n+1) - T(n) = \frac{1}{2^{n+1}}$$ hence if $T(n) = \frac{2^n-1}{2^n}$, then $$T(n+1) = T(n) + \frac{1}{2^{n+1}} = \frac{2^n-1}{2^n}+\frac{1}{2^{n+1}} = \frac{2(2^n-1)}{2^{n+1}}+\frac{1}{2^{n+1}} = \frac{2^{n+1}-2+1}{2^{n+1}},$$ giving the desired formula.

Since $T(1) = \frac{1}{2}=\frac{2-1}{2}$, the result is established by induction.

-
Great answer, but I don't have the intuition that $2*2^n$ is $2^{n+1}$. Is there a text I can review about exponent arithmetic to get a solid base on this? –  mirai May 4 '12 at 21:09
That's a basic rule of exponentiation: $a^ba^c = a^{b+c}$. If you don't see that, then you need to review basic algebra. –  Arturo Magidin May 4 '12 at 21:11
Will do, thanks. –  mirai May 4 '12 at 21:12

Just multiply the numerator and denominator in the first fraction by 2 and add the fractions.

-

We want to show that our sum is equal to $1-\frac{1}{2^n}$. The base step is easy. Let's do the induction step.

Suppose that the result holds when $n$ is the particular number $k$. We want to show that the result holds for the "next" $n$, namely $k+1$.

Look at the sum $$\frac{1}{2}+\frac{1}{2^2}+\cdots+\frac{1}{2^k}+\frac{1}{2^{k+1}}.$$ This is equal to $$\left(\frac{1}{2}+\frac{1}{2^2}+\cdots+\frac{1}{2^k}\right)+\frac{1}{2^{k+1}}.$$ By the induction hypothesis this is $$\left(1-\frac{1}{2^k}\right)+\frac{1}{2^{k+1}},$$ which is $$1-\left(\frac{1}{2^k}-\frac{1}{2^{k+1}}\right).$$

But $\dfrac{1}{2^k}-\dfrac{1}{2^{k+1}}=\dfrac{1}{2^{k+1}}$ (bring to the common denominator $2^{k+1}$), which completes the induction step.

Remarks: $1$. If we are not looking for a formal induction, note that our sum is equal to $$\left(1-\frac{1}{2}\right)+\left(\frac{1}{2}-\frac{1}{4}\right)+\left(\frac{1}{4}-\frac{1}{8}\right)+\cdots+\left(\frac{1}{2^{n-1}}-\frac{1}{2^n}\right).$$ Now remove the parentheses, and watch our sum collapse. The only survivors are the $1$ at the beginning and the $-\dfrac{1}{2^n}$ at the end.

$2.$ Amoroso ($A$) lives $1$ km from his beloved, who, naturally, lives at $B$. First, $A$ walks $\frac{1}{2}$ km towards $B$. Now $A$ is $\frac{1}{2}$ km from $B$.

Next, $A$ walks $\frac{1}{4}$ km towards $B$. Now, $A$ is $\frac{1}{4}$ km from $B$. Next, $A$ walks $\frac{1}{8}$ km towards $B$. Now $A$ is $\frac{1}{8}$ from $B$.

This pattern continues, until $A$ walks $\frac{1}{2^n}$ towards $B$. Now $A$ is $\frac{1}{2^n}$ from $B$. So the sum $\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots +\frac{1}{2^n}$ of his travels is $1-\frac{1}{2^n}$.

-
Thanks for the work :) –  mirai May 4 '12 at 21:07

Just in case you may be interested. More generally you can get a similar expression for such sums of powers of inverses. They basically come from the factorization

$$a^n - 1 = (a - 1)(a^{n-1} + a^{n-2} + \cdots + a + 1)$$

which can be proved by multiplying out the right hand side and then most of the terms cancel out and you'll be left with the expression on the left.

Then from this factorization, by dividing by $a - 1$ you get

$$\frac{a^n - 1}{a - 1} = a^{n-1} + a^{n-2} + \cdots + a + 1$$

Now by dividing by $a^n$ you get

$$\frac{a^n - 1}{a^{n}(a - 1)} = \frac{a^{n-1}}{a^n} + \frac{a^{n-2}}{a^n} + \cdots + \frac{a}{a^n} + \frac{1}{a^n}$$ $$= \frac{1}{a} + \frac{1}{a^2} + \cdots \frac{1}{a^{n-1}} + \frac{1}{a^n}$$

So that you have

$$\boxed{ \displaystyle\frac{a^n - 1}{a^{n}(a - 1)} = \frac{1}{a} + \frac{1}{a^2} + \cdots \frac{1}{a^{n-1}} + \frac{1}{a^n} }$$

Therefore the expression you want to prove by induction is obtained just by setting $a = 2$, but now you can give different values to $a$ and get similar expressions.

-
Thanks, that's an interesting finding! –  mirai May 5 '12 at 2:57

To prove that

$$\frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{2^n} = \sum_{k=1}^n \frac{1}{2^k} = \frac{2^n - 1}{2^n}$$

We can use two steps with telescopic induction.

This form of induction works as follows: To prove that

$$\sum_{k=1}^n f(k)=g(n)$$

Induction can be used to prove this equality by confirming the following two steps:

1. See if $f(1)=g(1)$ (base case)

2. See if $g(n+1)-g(n)=f(n+1)$

We shall let $f(x)=\frac{1}{2^x}$ and $g(x)=\frac{2^x - 1}{2^x}$. We confirm that

$$f(1)=\frac{1}{2^1}=g(1)=\frac{2^1-1}{2^1}=\frac{1}{2}$$

We then confirm that step 2 is true:

$$g(n+1)-g(n)= \frac{2^{n+1}-1}{2^{n+1}}-\frac{2^{n}-1}{2^{n}}= \frac{2^{n+1}-1}{2^{n+1}}-\frac{2(2^{n}-1)}{2^{n+1}}= \frac{2^{n+1}-1-2^{n+1}+2}{2^{n+1}}= \frac{1}{2^{n+1}}= f(n+1)$$

Thus confirming the equality.

-
Thanks, telescopic induction seems interesting. Is there a difference from standard induction? –  mirai May 4 '12 at 21:10
@mirai There is a slight difference. Telescopy uses the difference between $g(x+1)$ and $g(x)$ to isolate the $n+1$ th term of the sum. For example, if $$g(n)=1+2+ \cdots +n = \frac{n(n+1)}{2}$$ clearly $$g(n+1)-g(n)=1+2+\cdots+n+(n+1)- (1+2+\cdots+n)=\frac{(n+1)(n+2)}{2}-\frac{n(n+1)}{2}=n+1$$ Because we know the n+1th term is $n+1$ which is what we get with the series, the equality is proven. –  Argon May 4 '12 at 21:48

For what is worth:

$$S_n = \frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{{{2^n}}}$$

Then

$$\frac{{{S_n}}}{2} = {S_n} + \frac{1}{{{2^{n + 1}}}} - \frac{1}{2} \Rightarrow {S_n} = 2{S_n} + \frac{1}{{{2^n}}} - 1 \Rightarrow 1 - \frac{1}{{{2^n}}} = {S_n}$$

-
Thanks, but I don't see the $\frac{2^n-1}{2^n}$ equality anywhere. Is this a different approach? –  mirai May 4 '12 at 21:24
@mirai $$1 - \frac{1}{{{2^n}}} = \frac{{{2^n}}}{{{2^n}}} - \frac{1}{{{2^n}}} = \frac{{{2^n} - 1}}{{{2^n}}}$$ –  Pedro Tamaroff May 4 '12 at 21:25
That's clever, thanks again. –  mirai May 4 '12 at 21:26