College Algebra, Chapter 9, 9.5, Section 9.5, Problem 14

Prove that the formula $\displaystyle 1 + 2 + 2^2 + ... + 2^{(n - 1)} = 2^n - 1$ is true for all natural numbers $n$.

By using mathematical induction,

Let $P(n)$ denote the statement $\displaystyle 1 + 2 + 2^2 + ... + 2^{(n - 1)} = 2^n - 1$.

Then, we need to show that $P(1)$ is true. So,


$
\begin{equation}
\begin{aligned}

1 =& 2^{(1)} - 1
\\
1 =& 2 - 1
\\
1 =& 1

\end{aligned}
\end{equation}
$


Thus, we prove the first principle of the mathematical induction. More over, assuming that $P(k)$ is true, then

$\displaystyle 1 + 2 + 2^2 + ... + 2^{k - 1} = 2^k - 1$

Now, by showing $P(k + 1)$, we have

$1 + 2 + 2^2 + ... + 2^{k - 1} + 2^{(k + 1) - 1} = 2 ^{(k + 1)}-1$

We start with the left side and use the induction hypothesis to obtain the right side of the equation:


$
\begin{equation}
\begin{aligned}

=& \left[ 1 + 2 + 2^2 + ... 2^{k - 1} \right] + \left[ 2^{(k + 1) - 1} \right]
&& \text{Group the terms}
\\
\\
=& 2^k - 1 + 2^{(k + 1) - 1}
&& \text{Induction hypothesis}
\\
\\
=& 2^k -1 + 2^k
&& \text{Simplify}
\\
\\
=& 2 \cdot 2^k - 1
&& \text{Rewrite the term}
\\
\\
=& 2^{(k + 1)} - 1
&& \text{Apply the properties of exponents}

\end{aligned}
\end{equation}
$


Therefore, $P(k+1)$ follows from $P(k)$, and this completes the induction step.