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 F_{1}, F_{2}, … F_{n}, …, then we can express the sequence via the recurrence relation x_{n}=x_{n-1}+x_{n-2}, with initial conditions x_{0}=0, x_{1}=1.
The relation x_{n}=x_{n-1}+x_{n-2} is a second-degree, homogeneous, linear recurrence relation with constant coefficients. Thus, if we find independent solutions x_{n} and y_{n} 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 x_{n}=r^{n}. Plugging this into our particular equation:
x_{n}=x_{n-1}+x_{n-2}
r^{n}=r^{n-1}+r^{n-2}
r^{n}–r^{n-1}–r^{n-2}=0
In this last equation, we can factor out r^{n-2}, giving us the condition
r^{2}–r-1=0
independent of n. This quadratic equation has roots . Thus, the general solution to x_{n}=x_{n-1}+x_{n-2} is
,
where C_{+} and C_{–} are constants.
For the Fibonacci sequence, the initial conditions are x_{0}=0, x_{1}=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 F_{n} as:
.
First, we note that and . Thus, for large n, x_{n} 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 | x_{n} | x_{n+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 |
Tags: Fibonacci, Fibonacci Sequence, Golden Mean, Golden Ratio, Math, Monday Math, Recurrence Relation
Leave a Reply