I Finding a general formula for a recursive sequence

AI Thread Summary
The discussion explores finding a general formula for recursive sequences, particularly focusing on the Fibonacci sequence defined by an = an-1 + an-2. It explains that the characteristic equation, derived from assuming a solution of the form an = x^n, is essential for solving such recurrences. For the Fibonacci sequence, the characteristic equation is x^2 - x - 1 = 0, which yields roots related to the golden ratio. The general solution can be expressed as a linear combination of these roots, allowing for the determination of specific terms using initial conditions. This method parallels techniques used in solving nth order linear homogeneous differential equations.
Trollfaz
Messages
143
Reaction score
14
The general formula for the nth term of the Fibonacci sequence where an=an-1+an-2 can determined by matrix diagonalizations
Is there a way to determine the formula of any recursive sequence say
an=a1+a2+...an-1
 
Mathematics news on Phys.org
Trollfaz said:
The general formula for the nth term of the Fibonacci sequence where an=an-1+an-2 can determined by matrix diagonalizations
Is there a way to determine the formula of any recursive sequence say
an=a1+a2+...an-1
https://en.wikipedia.org/wiki/Linear_recurrence_with_constant_coefficients

You solve these by finding the characteristic equation, solving that and using it to derive solutions as a linear combination of exponentials (or, when the solutions involve complex numbers, of sines, cosines and exponentials).

For Fibonacci: ##a_n=a_{n-1} + a_{n-2}##, the characteristic equation is ##x^2=x+1##. The characteristic equation can be found by assuming that the solution takes the form: ##a_n=x^n## and expressing the recurrence in terms of ##x##.

This recurrence has two terms on the right, so it is second order. Its characteristic equation is a quadratic. A recurrence with n terms on the right is "nth order". The chacteristic equation will be a polynomial equation of the nth degree.

So one has the polynomial equation in standard form: ##x^2 - x - 1 = 0##. This is a quadratic, so we can solve it with the quadratic formula to obtain ##x=\frac{-b \pm \sqrt{b^2-4ac}}{2a}##. The two roots should be approximately 1.61803 and -0.61803. Call these ##r_1## and ##r_2##. [These turn out to be the golden ratio ##\phi## and the additive inverse of its reciprocal. The matching decimal digits is not a coincidence. It is one of the properties of the golden ratio].

The solution to the original Fibonacci recurrence will be a linear combination: ##a_n = k_1{r_1}^n + k_2{r_2}^n##. If you have the two starting terms for the recurrence, you can solve a set of simultaneous equations (via matrix algebra if you like) for ##k_1## and ##k_2##.

The starting terms were referred to as "boundary conditions" when I learned this stuff. It is very much akin to solving nth order linear homogenous differential equations.
 
Last edited:
  • Like
  • Informative
Likes DrClaude and mfb
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Is it possible to arrange six pencils such that each one touches the other five? If so, how? This is an adaption of a Martin Gardner puzzle only I changed it from cigarettes to pencils and left out the clues because PF folks don’t need clues. From the book “My Best Mathematical and Logic Puzzles”. Dover, 1994.
Thread 'Imaginary Pythagoras'
I posted this in the Lame Math thread, but it's got me thinking. Is there any validity to this? Or is it really just a mathematical trick? Naively, I see that i2 + plus 12 does equal zero2. But does this have a meaning? I know one can treat the imaginary number line as just another axis like the reals, but does that mean this does represent a triangle in the complex plane with a hypotenuse of length zero? Ibix offered a rendering of the diagram using what I assume is matrix* notation...

Similar threads

Back
Top