Recurrence relation $a_{n+1} = 2 a_n -1$ with $a_0=3$. What is $a_n$ expressed as a function of $n$? 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 an = (some expression) but how to handle this type of problem in the form an+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!
 A: 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!
A: 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.
A: 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.$$
A: 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$.
A: 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$.
