Thread: Finding Explicit formula for a recursion

how would one go about finding the explicit formula for a_n = 2a_(n-1) - a_(n-3) given a_1=2, a_2=3, a_3=5?

Please help, need to get answer quickly! Thanks.

Do you know the characteristic equation method of solving recurrences?

Rewrite the recurrence as a_n - 2a_(n-1) + a_(n-3) = 0
Characteristic equation is r^3 - 2r^2 + 1 = 0
Find all solutions for r.
You should find 3 different roots r_1, r_2, r_3.

Your final formula is a_n = A*r_1^n + B*r_2^n + C*r_3^n

Now use the initial conditions to find A, B, and C.

See if you can prove, perhaps by induction, that this is really just the Fibonacci sequence (without the initial 0,1,1). Then I suppose it's a question of an exact formula for the Fibonacci numbers.

Is it fibonnacci? Because inital sequence 1,3,5 is already not Fibonnaci.

[Never mind]

Originally Posted by snowtea

Is it fibonnacci? Because inital sequence 1,3,5 is already not Fibonnaci.

The initial sequence is 2,3,5.

Yeah, your right. I must be dislexic today.
That's what happens when they don't latexify their mathematics

Your right, it does look like Fibonnaci. I think it is because a_(n-1) - a_(n-3) = a_(n-2) for this set of initial conditions.
Note the recurrence is only Fibonnaci because of the initial conditions provided. Given numbers like 1,2,5 it will no longer be Fibonnaci.

But still the explicit formula for Fibonnaci is quite ugly

Originally Posted by snowtea

Yeah, your right. I must be dislexic today.
That's what happens when they don't latexify their mathematics

Your right, it does look like Fibonnaci. I think it is because a_(n-1) - a_(n-3) = a_(n-2) for this set of initial conditions.
Note the recurrence is only Fibonnaci because of the initial conditions provided. Given numbers like 1,2,5 it will no longer be Fibonnaci.

But still the explicit formula for Fibonnaci is quite ugly

Well... I doubt as if he will find a simpler one. If there were a simpler one, then... well, it would.. already.. be simpler.

problem solved, thanks for all the responses