<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] 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}$. 
</s>