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