# Finding Explicit formula for a recursion

• Dec 15th 2010, 04:58 PM
bonobos
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?

• Dec 15th 2010, 05:18 PM
snowtea
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.
• Dec 15th 2010, 05:22 PM
topspin1617
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.
• Dec 15th 2010, 05:28 PM
snowtea
Is it fibonnacci? Because inital sequence 1,3,5 is already not Fibonnaci.

[Never mind]
• Dec 15th 2010, 05:30 PM
topspin1617
Quote:

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

The initial sequence is 2,3,5.
• Dec 15th 2010, 05:40 PM
snowtea
Yeah, your right. I must be dislexic today. :p
That's what happens when they don't latexify their mathematics :D

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 :)
• Dec 15th 2010, 06:33 PM
topspin1617
Quote:

Originally Posted by snowtea
Yeah, your right. I must be dislexic today. :p
That's what happens when they don't latexify their mathematics :D

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.
• Dec 15th 2010, 07:44 PM
bonobos
problem solved, thanks for all the responses