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

• Is your question: how to create a closed form for this recurrence relation? In any case please update your post with a question. Also if you write down the first few $a_i$ you'll see a series that is easy to specify with a function. – Χpẘ Apr 9 '17 at 0:12

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

• I don't see how the second line follows from the first – mrnovice Apr 9 '17 at 0:20
• @mrnovice because for relations like $b_n = 2b_{n-1}$ we now the form of general solution, right? It is $b_n = 2^nb_0$ (as was written in the original question). Thus, we can simply substitute $b_n = a_{n} + 1$ in the first relation and get the second one. – Swistack Apr 9 '17 at 0:32

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

• I haven't thought of solving it this way before but it makes a lot of sense, thanks – fzero24 Apr 9 '17 at 0:29

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

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