Many people are familiar with the Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, …, where the first two terms are both one, and each subsequent term is the sum of the previous two terms. If we express this as F1, F2, … Fn, …, then we can express the sequence via the recurrence relation xn=xn-1+xn-2, with initial conditions x0=0, x1=1.
The relation xn=xn-1+xn-2 is a second-degree, homogeneous, linear recurrence relation with constant coefficients. Thus, if we find independent solutions xn and yn to the equation, then any linear combination of them is also a solution (this is fairly simple to check for yourself).
To find an explicit formula for a homogeneous linear recurrence relation with constant coefficients, try a solution of the form xn=rn. Plugging this into our particular equation:
In this last equation, we can factor out rn-2, giving us the condition
independent of n. This quadratic equation has roots . Thus, the general solution to xn=xn-1+xn-2 is
where C+ and C– are constants.
For the Fibonacci sequence, the initial conditions are x0=0, x1=1. Plugging the first into the general equation:
and the second gives us:
Solving this linear system for C+ and C– gives and , and so
Now we note that r+ is the golden ratio φ≈1.6180, and that . Thus, we can write Fn as:
First, we note that and . Thus, for large n, xn is approximately , and so we see the famous result that the ratio of sucessive terms of the Fibonacci sequence approach the golden ratio:
Here is a table illustrating this: