# 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? May 4, 2012 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. May 4, 2012 at 20:53
• Multiply by $\frac{2}{2}$ to get a common denominator, then add. May 4, 2012 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}}.$$ May 4, 2012 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? May 4, 2012 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. May 4, 2012 at 21:11
• Will do, thanks. May 4, 2012 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}$.

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! May 5, 2012 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? May 4, 2012 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. May 4, 2012 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? May 4, 2012 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
May 4, 2012 at 21:25
• That's clever, thanks again. May 4, 2012 at 21:26