# Closed formula given with reccurent formula

I do have an answer and description from the professor, but I couldn't understand his solution. Can anyone give me an answer and elaborate on how I'm supposed to prove this.

-
Do a proof by induction, are you familiar with this method of proof? –  EgoKilla May 9 '14 at 1:26
What does this have to do with Fibonacci numbers? –  Steven Stadnicki May 9 '14 at 1:36

We have $a_{n+1} = 3a_n - 2 \implies a_{n+1} - 1 = 3(a_n-1)$. Calling $a_n-1$ as $b_n$, we get $$b_{n+1} = 3b_n \implies b_n = 3^{n-1} b_1$$ We have $b_1 = a_1-1 = 4-1 = 3$. Hence, $b_n = 3^n$. Hence, $a_n = 3^n+1$.

-

Base case: $n=1$, we have $a_1=4=3^1+1$.

Now the induction step.

Assume $$3a_{n-1}-2 = 3^n+1$$ to prove $$3a_{(n+1)-1}-2 = 3^{n+1}+1.$$

-

Another approach is to use a matrix to represent the recursion, which you can do, since the recursion is linear. Then try diagonalizing the matrix.

-