Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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$.

share|cite|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|cite|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|cite|improve this answer

Your Answer


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.