Proof by Induction for a recursive sequence and a formula

For the setup, we need to assume that $a_n = 2^n - 1$ for some $n$, and then show that the formula holds for $n + 1$ instead. That is, we need to show that $$a_{n + 1} = 2^{n + 1} - 1$$

Let's just compute directly:

\begin{align*} a_{n + 1} &= 2a_n + 1 \hspace{1.55in}\text{// recursion relation} \\ &= 2 \cdot (2^n - 1) + 1 \hspace{1in} \text{// induction hypothesis} \\ &= 2^{n + 1} - 2 + 1 \hspace{1.15in} \text{// arithmetic} \\ &= 2^{n + 1} - 1 \end{align*}

which is exactly what we wanted to be true.