Recurrence relation $a_{n+1} = 2 a_n -1$ with $a_0=3$. What is $a_n$ expressed as a function of $n$?

Question

I'm having a hard time finding an explanation how to solve the following problem.

Given the recurrence relation $a_{n+1} = 2 a_n -1$ with $a_0=3$. What is $a_n$ when expressed as an explicit function of $n$?

Supposedly the correct answer is $a_n = 2^{n+1}+1$. But what is the step by step approach to arrive at this solution? All of the resources I've found begin with a recurrence relation in the form a_n = (some expression) but how to handle this type of problem in the form a_n+1 = (some expression) ?

Is it a matter of moving the variable to the other side and then solving iteratively? Or is there some clever/magic approach we should use here? Super appreciate if anyone can detail the steps to take to arrive at the correct solution.

Thanks in advance!

Answer 1

First way

Verify by induction that the provided solution is the right one...

Second way

If you don't know the solution. Take $b_n = a_n +c$ in order to get rid of the term $-1$ in the recurrence relation. That gives

$$b_{n+1}- c = 2 (b_n-c) -1$$ and therefore $b_{n+1} = 2 b_n$ if $c=-1$. The relation $b_{n+1} = 2b_n$ is easy to solve in $b_n = 2^n b_0$ and finally $a_n = 2^n (a_0-1) + 1 = 2^{n+1} + 1$ knowing that $a_0=3$.

This solution avoids guessing!

Answer 2

First of all note that assuming the form of recurrence, the answer is linear. Assume $a_n=na+b$ and assert it into the condition: $na+a+b=2na+2b-1$ and also $a_0=b=3$ so $b=3$ and $a=2$.

Answer 3

You can compute the first terms:

• $a_0=3$;
• $a_1=5$;
• $a_2=9$;
• $a_3=17$
• $\vdots$

These numbers are $2+1$, $2^2+1$, $2^3+1$, $2^4+1$, and so on, which suggests that $a_n=2^{n+1}+1$. And now you can prove by induction that this is indeed correct.

Answer 4

The additional $+1$ is annoying, but can be gotten rid of. Let $b_n=a_n+c$ for a constant $c$ (that we do not know yet). Equivalently, $a_n=b_n-c$, so the recursion formula becomes $$ b_{n+1}-c = 2(b_n-c)-1$$ or: $$ b_{n+1}=2b_n-(c+1).$$ Now if we let $c=-1$, the recursion simplifies to $$ b_{n+1}=2b_n$$ from which we easily guess (and verify) that $$ b_n=2^nb_0,$$ where $b_0=a_0+c=3-1=2$ so that explcitly $$b_n=2^n\cdot 2=2^{n+1} $$ and $$ a_n=b_n-1=2^{n+1}+1.$$

Answer 5

Get rid of $-1$ by taking $$a_{n+1}=2a_n-1$$

minus $$a_{n}=2a_{n-1}-1$$

to get $$a_{n+1}-a_n=2a_n-2a_{n-1}$$

or $$a_{n+1}-3a_n+2a_{n-1}=0.$$

The characteristic equation is $r^2-3r+2=(r-1)(r-2)$, so $a_n=C+D2^n$.

You can solve for $C$ and $D$ using $a_0=3$ and $a_1=5$.