Proof sequence by induction

Question

I have the following problem I am not sure about. Let n = 0, 1, 2, ... and show that the equation $a_0 = 1, a_{n+1} = 2a_{n} + 1$

has the solution $ a_n = 2^n - 1$

Base case: $ n = 0 \\ a_0 = 2^0 - 1 = 0$

Now what exactly do I proof? I tried doing something like this but $2^n - 1 = 2a_{n} + 1$ but I cannot make it equal.

Answer 1

Hint

Observe that $$a_{n+1}+1=2(a_n+1)$$

$$=\cdots=2^{n-r}(a_r+1)$$ where $n\ge r\ge0$

By induction if $a_n=2^n-1,$

$$a_{n+1}+1=2(2^n)$$

Answer 2

Assume $a_n = 2^n-1$. Then show that $a_{n+1} = 2^{n+1} - 1$ based on that premise. Alongside the base case, that completes the induction proof.

---

Hint:

Notice that $a_{n+1} = 2a_n + 1$ per the recurrence relation.

Answer 3

By induction, if $a_{n + 1} = 2a_n + 1$ has the solution $a_n=2^n - 1$ for $n = 0, 1, 2, ...$, then is must also hold for $n + 1$ so that $a_{n + 1} = 2^{n + 1} - 1$.

We can insert the hypothesis ($a_n=2^n - 1$) into the recurrence with the inductive value $n$

$a_{n+1} = 2a_n+1=2(2^n - 1) + 1 = 2 * 2^n - 2 + 1 = 2 * 2^n - 1 = 2^{n + 1} - 1$.