$a_n=2a_{n-1}+1$; prove $a_n+1=2^n(a_0+1)$

Question

If the sequence $a_n$ satisfies $a_n = 2a_{n-1}+1$ for all $n \geq 1$, show that for every $n \geq 0$, we have $a_n+1 = 2^n(a_0+1)$.

I thought of letting $a_n = c^n$ and $a^{n-1} = c^{n-1}$ then solving that way, but the extra $1$ makes it difficult.

Answer 1

HINT: $$a_n=2a_{n-1}+1$$ $$a_n+1=2a_{n-1}+2=2(a_{n-1}+1)$$ $$a_n+1=2(a_{n-1}+1)=2^2(a_{n-2}+1)$$ and so on.

Can you prove now?