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.

Printable View

- Dec 15th 2010, 05:58 PMbonobosFinding 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. - Dec 15th 2010, 06:18 PMsnowtea
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, 06:22 PMtopspin1617
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, 06:28 PMsnowtea
Is it fibonnacci? Because inital sequence 1,3,5 is already not Fibonnaci.

[Never mind] - Dec 15th 2010, 06:30 PMtopspin1617
- Dec 15th 2010, 06:40 PMsnowtea
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, 07:33 PMtopspin1617
- Dec 15th 2010, 08:44 PMbonobos
problem solved, thanks for all the responses