Question

What is the solution for the recurrence relation a_n=2a_{n−1}−1

an

​=2an−1

​−1 with a_1=3

a1

​=3 .

Answer 1

$a_n=2a_{n-1}-1=2\left( 2a_{n-2}-1 \right) -1=2^2\cdot a_{n-2}-\left( 1+2 \right) =\\=...=2^{n-1}a_1-\left( 1+2+...+2^{n-2} \right) =2^{n-1}\cdot 3-\frac{2^{n-1}-1}{2-1}=\\=3\cdot 2^{n-1}-2^{n-1}+1=2^n+1$