## Monday Math 36

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:
xn=xn-1+xn-2
rn=rn-1+rn-2
rnrn-1rn-2=0
In this last equation, we can factor out rn-2, giving us the condition
r2r-1=0
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:

n xn xn+1 
1 1 1 1
2 1 2 2
3 2 3 1.5
4 3 5 1.6667
5 5 8 1.6
6 8 13 1.625
7 13 21 1.6154
8 21 34 1.6190
9 34 55 1.6176
10 55 89 1.6182