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?
 A: 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.
A: Just multiply the numerator and denominator in the first fraction by 2 and add the fractions.
A: 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}$. 
A: 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.
A: 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:


*

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

*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.
A: 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}$$
