# Thread: Need Help Fiinding Recursive formula

1. ## Need Help Fiinding Recursive formula

I need help finding a definate formula for the sequence described below.

a_1=2

a_2=5

a_(n+2) = 3a_(n+1) - 2a_n

It is very similar to the Fibonacci sequence.
Here is as far as I got.

x^n = (x^2 - 3x +2) = 0

x = 2, 1

Now I need to use these numbers to come up with a formula.

2. ## Re: Need Help Fiinding Recursive formula

Since the characteristic roots are 1 and 2, you can expect the closed form to be:

$x_n=k_1\cdot1^n+k_2\cdot2^n=k_1+k_2\cdot2^n$

then use your known (initial) values to determine the coefficients $k_i$.

3. ## Re: Need Help Fiinding Recursive formula

Sorry, but I just can't seem to understand this any more than what I have already done. What is the final formula that I should come up with? Maybe if I know the formula, I can understand how to get there. Where did "k" come from?

4. ## Re: Need Help Fiinding Recursive formula

Originally Posted by nish915
Where did "k" come from?
As Mark said,
Originally Posted by MarkFL2
use your known (initial) values to determine the coefficients $k_i$.
$k_i$ are some constants, yet undetermined. You can substitute n = 1 and n = 2 into the equation in post #2 (where $x_n$ should be replaced with $a_n$) to get two linear equations in $k_1$ and $k_2$. For more information on linear recurrence relation see here and here.

5. ## Re: Need Help Fiinding Recursive formula

Thank you both for the help. I just figured it out. The final equation is (3/2)(2^n) - 1.

6. ## Re: Need Help Fiinding Recursive formula

Hello, nish915!

$\text{given: }\:a(1)\:=\:2,\;\;a(2)\:=\:5 ,\;\;a(n+2) \:=\: 3a(n+1) - 2a(n)$

$\text{Find a closed form for }a(n).$

We have: . $a(n+2) - 3a(n+1) + 2a(n) \:=\:0$

Let $X^n = a(n)\!:\;X^{n+2} - 3X^{n+1} + 2X^n \:=\:0$

Divide by $X^n\!:\;\;X^2 - 3X + 2 \:=\:0 \quad\Rightarrow\quad (X - 1)(X - 2) \:=\:0 \quad\Rightarrow\quad X \:=\:1,2$

The function is of the form: . $a(n) \:=\:A(1^n) + B(2^n) \:=\:A + 2^nB$

Then we have: . $\begin{array}{cccccccccc} a(1) = 2: & A + 2B &=& 2 & [1] \\ a(2) = 5: & A + 4B &=& 5 & [2] \end{array}$

Subtract [2]-[1]: . $2B \,=\,3 \quad\Rightarrow\quad B \,=\,\tfrac{3}{2}$

Substitute into [1]: . $A + 2(\tfrac{3}{2}) \:=\:2 \quad\Rightarrow\quad A \:=\:\text{-}1$

Therefore: . $a(n) \;=\;\text{-}1 + \tfrac{3}{2}\!\cdot\!2^n \;=\;3\!\cdot\!2^{n-1} - 1$

7. ## Re: Need Help Fiinding Recursive formula

Originally Posted by nish915
Thank you both for the help. I just figured it out. The final equation is (3/2)(2^n) - 1.
Yes, and as Soroban did, I would choose to write:

$a_n=3\cdot2^{n-1}-1$

to get integral coefficients. It just looks cleaner.