Discrete Mathematics – How to Solve a_n = 2a_{n-1} + 1, a_0 = 0, a_1 = 1

discrete mathematicsrecurrence-relations

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

Best Answer

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

Related Question