2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Χpẘ Apr 9 '17 at 0:12
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I don't see how the second line follows from the first $\endgroup$ – mrnovice Apr 9 '17 at 0:20
  • 1
    $\begingroup$ @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. $\endgroup$ – Swistack Apr 9 '17 at 0:32
5
$\begingroup$

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

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

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.