<s>[INST] 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?
 [/INST] 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.
</s>