Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

enter image description here

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.

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

3 Answers 3

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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