<s>[INST] How to solve $a_n = 2a_{n-1} + 1, a_0 = 0, a_1 = 1$? $a_n = 2a_{n-1} + 1, a_0 = 0, a_1 = 1$
So to get the closed form of this recurrence relation, I would usually try to get it into the form of $a_n = ra_{n-1}$ and then $a_n = r^na_0$. But what am I supposed to do with the $1$?
Thanks!
 [/INST] $a_2=2\cdot 1+1=3=2^2-1,\quad a_3=2\cdot 3+1=7=2^3-1,\quad a_4=2\cdot7+1=15=2^4-1,\quad a_5=2\cdot 15+1=31=2^5-1$
So in general we guess that $a_{n}=2^n-1,\quad n\in\mathbb{N}$
So we know it's true for $n=0$
Assume true for $n$, now we must prove true for $n+1$:
$a_{n+1} = 2\cdot a_n+1=2\cdot(2^n-1)+1=2^{n+1}+1$ as required, hence true for $n+1$, hence true $\forall n\in\mathbb{N}$
Therefore we conclude that $a_n=2^n-1$
</s>