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!
 A: It should be clear that if you solve,
$$L=2L+1$$
You get the following,
$$-1=2(-1)+1 \tag{1}$$
We want to solve,
$$a_{n}=2a_{n-1}+1 \tag{2}$$
Subtracting equation $1$ from $2$ gives,
$$(a_{n}+1)=2(a_{n-1}+1)$$
Let $b_{n}=a_{n}+1$ so that $b_0=a_0+1$ and $a_n=b_n-1$ then we have,
$$b_{n}=2b_{n-1}$$
Then continue and back substitute.
$$b_{n}=b_02^n$$
$$b_{n}=(a_0+1)2^n$$
$$a_{n}=b_n-1=(a_0+1)2^n-1$$
$$a_{n}=2^n-1$$
A: If we write out the first few terms, you can see a pattern.
$$0,1,3,7,15,31,63$$
All of the numbers are of the form $a_n=2^n-1$. The way we can see this from the recurrence is through induction: $$2(2^{n-1}-1)+1 = 2^n -1$$
Now try evaluating $a_n=3a_{n-1}+2$, and then $a_n=ka_{n-1}+k-1$.
A: $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$
A: Note that
$$a_n + 1 = 2(a_{n-1} + 1)$$
Then you can conclude that $a_n + 1 = 2^n(a_0 + 1) = 2^n$, which means that $a_n = 2^n - 1$.
Generally speaking, if you solve an equation
$$a_n = ka_{n-1} + r$$
there can be two cases.
Case 1. $k \neq 1$
Then this relation can be rewritten as $a_n + \dfrac{r}{k-1} = k\left(a_{n-1} + \dfrac{r}{k-1}\right)$, which means that $a_n = k^n\left(a_0 + \dfrac{r}{k-1}\right) - \dfrac{r}{k-1}$
Case 2. $k = 1$
Then $a_n = a_{n-1} + r$ and the solution is simply $a_n = rn + a_0$.
