How to solve $a_n = 2a_{n-1} + 1, a_0 = 0, a_1 = 1$?

Question

$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!

Answer 1

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$.

Answer 2

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$.

Answer 3

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$$

Answer 4

$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$