The Fibonacci SequencePhilip J. ErdelskyAugust 30, 2012 |
Please e-mail comments, corrections and additions to the webmaster at pje@efgh.com.
The Fibonacci sequence is the sequence of integers constructed according to the following two rules:
It is easy to calculate the first few terms:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
The closed form for the n-th term of the Fibonacci sequence (where the first term is number 0) is
(1) [(½ + ½ √ 5)^{ n} - (½ - ½ √ 5)^{ n}]/√5.
At this point, most people want to know where the closed form came from. It can be verified by mathematical induction, but it seems too complicated to have arisen from such simple rules.
Actually, the derivation is fairly simple. Consider a sequence with a recurrence relation even simpler than the Fibonacci relation. The rules are as follows:
Given the common ratio r, it is easy to write the terms of the sequence:
1, r, r^{ 2}, r^{ 3}, ...
The closed form for the n-th term of this sequence is simple and obvious: r^{ n}.
Now we ask the crucial question. Is there any value of the common ratio r for which this sequence also obeys the Fibonacci recurrence relation? If so, then
r^{ n+2} = r^{ n+1} + r^{ n}.
Since r ≠ 0, we can divide both sides of this equation by r^{ n} to obtain:
r^{ 2} = r + 1.
This is a simple quadratic equation whose two roots are
(2) r_{1} = ½ + ½ √ 5,
(3) r_{2} = ½ - ½ √ 5,
Hence each of the following obeys the Fibonacci recurrence relation:
1, r_{1}, r_{1}^{ 2}, r_{1}^{ 3}, ...
1, r_{2}, r_{2}^{ 2}, r_{2}^{ 3}, ...
Now we write the Fibonacci recurrence relation for these sequences:
r_{1}^{ n+2} = r_{1}^{ n+1} + r_{1}^{ n},
r_{2}^{ n+2} = r_{2}^{ n+1} + r_{2}^{ n}.
If we multiply the first equation by a, multiply the second equation by b, and add the results, we obtain
ar_{1}^{ n+2} + br_{2}^{ n+2} = ar_{1}^{ n+1} + br_{2}^{ n+1} + ar_{1}^{ n} + br_{2}^{ n}.
This is the Fibonacci recurrence relation for the sequence whose n-th term is
(4) ar_{1}^{ n} + br_{2}^{ n}.
However, this sequence may not have the Fibonacci initial values. For that, we must choose a and b so that
a+b = 0,
ar_{1} + br_{2} = 1.
The solution of this system is
(5) a = 1 / (r_{1} - r_{2}) = 1/√5,
(6) b = -1 / (r_{1} - r_{2}) = -1/√5.
The closed form (1) for the n-th term of the Fibonacci sequence is then obtained by substituting (2), (3), (5) and (6) into (4).
The ratio of consecutive terms of the Fibonacci sequence appears to tend to a limit:
1/1 = 1, 2/1 = 2, 3/2 = 1.5, 5/3 = 1.667, 8/5 = 1.6, 13/8 = 1.625, 21/13 = 1.615, 34/21 = 1.619, ...
In fact, the limit is precisely ½ + ½ √ 5, which is approximately 1.61803. This can be seen from the closed form (1), which lets us write the ratio of consecutive terms as
(½ + ½ √ 5)^{ n+1} - (½ - ½ √ 5)^{ n+1}
--------------------------------------------
(½ + ½ √ 5)^{ n} - (½ - ½ √ 5)^{ n}
If we divide both numerator and denominator by (½ + ½ √ 5)^{ n}, this becomes
½ + ½ √ 5 - (½ - ½ √ 5) s^{ n+1}
--------------------------------------
1 - s ^{ n}
where s = (½ - ½ √ 5) / (½ + ½ √ 5) ≅ -0.381967. Since |s| < 1, the terms containing s tend to zero as n increases without bound, and the ratio tends to ½ + ½ √ 5.
The same technique can be used to find a closed form for any sequence whose recurrence relation is linear with constant coefficients.
In general, such a sequence is defined as follows:
Here we require that c_{m} ≠ 0, but the other coefficients may be zero.
Proceeding as in the Fibonacci case, we find that the sequence whose n-th term is r^{ n} obeys the recurrence relation if
r^{ m} = c_{1}r^{ m-1} + c_{2}r^{ m-2} + c_{3}r^{ m-3} + ... + c_{m-1}r + c_{m}.i.e., if r is a root of the m-th degree polynomial
(7) r^{ m} - c_{1}r^{ m-1} - c_{2}r^{ m-2} - c_{3}r^{ m-3} - c_{m-1}r - ... - c_{m} = 0.
Since c_{m} ≠ 0, none of the roots is zero.
If this polynomial has m distinct roots r_{1}, r_{2}, ... r_{m}, the desired closed form is
(8) x_{n} = a_{1} r_{1}^{ n} + a_{2} r_{2}^{ n} + a_{3} r_{3}^{ n} + ... + a_{m} r_{m}^{ n}.where the coefficients a_{1}, a_{2}, a_{3}, ... a_{m} are the solutions to
(9) a_{1} + a_{2} + a_{3} + ... + a_{m} = x_{0}
a_{1} r_{1} + a_{2} r_{2} + a_{3} r_{3} + ... + a_{m} r_{m} = x_{1}
a_{1} r_{1}^{ 2} + a_{2} r_{2}^{ 2} + a_{3} r_{3}^{ 2} + ... + a_{m} r_{m}^{ 2} = x_{2}
***
a_{1} r_{1}^{ m-1} + a_{2} r_{2}^{ m-1} + a_{3} r_{3}^{ m-1} + ... + a_{m} r_{m}^{ m-1} = x_{m-1}
The matrix of this system is the transpose of a square Vandermonde matrix, which is known to be nonsingular (see the Appendix).
What if the polynomial (7) has one or more multiple roots? There will not be enough equations in the system (9) to guarantee a solution. Clearly, some modification is needed.
We can write the recurrence relation for the sequence whose n-th term is r^{ n} as follows:
r^{ n} - c_{1}r^{ n-1} - c_{2}r^{ n-2} - c_{3}r^{ n-3} - ... - c_{m}r^{ n-m} = 0.
This polynomial has a zero root of multiplicity n-m, but we are not interested in that root. A nonzero double root of this polynomial is also a root of its derivative:
nr^{ n-1} - (n-1)c_{1}r^{ n-2} - (n-2)c_{2}r^{ n-3} - (n-3)c_{3}r^{ n-4} - ... - (n-m)c_{m}r^{ n-m-1} = 0.
Hence the sequence {0, 1, 2r, 3r^{ 2}, ...}, whose n-th term is nr^{ n-1}, also obeys the recurrence relation in this case.
Therefore, if r_{1} is a double root, and r_{2}, r_{3}, ... r_{m-1} are the other roots, the closed form (8) becomes
x_{n} = a_{1} r_{1}^{ n} + a_{2} nr_{1}^{ n-1} + a_{3} r_{2}^{ n} + ... + a_{m} r_{m-1}^{ n}.
The system (9) becomes:
a_{1} + 0 + a_{3} + ... + a_{m} = x_{0}
a_{1} r_{1} + a_{2} + a_{3} r_{2} + ... + a_{m} r_{m-1} = x_{1}
a_{1} r_{1}^{ 2} + a_{2} 2r_{1} + a_{3} r_{2}^{ 2} + ... + a_{m} r_{m-1}^{ 2} = x_{2}
a_{1} r_{1}^{ 3} + a_{2} 3r_{1}^{ 2} + a_{3} r_{2}^{ 3} + ... + a_{m} r_{m-1}^{ 3} = x_{2}
***
a_{1} r_{1}^{ m-1} + a_{2} (m-2)r_{1}^{ m-2} + a_{3} r_{2}^{ m-1} + ... + a_{m} r_{m-1}^{ m-1} = x_{m-1}
The matrix of this system is the transpose of a square confluent Vandermonde matrix, which is known to be nonsingular (see the Appendix).
If there are other double roots, they can be handled in the same way.
Roots of higher multiplicity can be handled similarly, using higher-order derivatives.
A square Vandermonde matrix is a matrix V whose rows are geometric progressions of the following form:
| 1, r_{1}, r_{1}^{ 2}, r_{1}^{ 3}, ..., r_{1}^{ n-1} |
| 1, r_{2}, r_{2}^{ 2}, r_{2}^{ 3}, ..., r_{2}^{ n-1} |
V = | 1, r_{3}, r_{3}^{ 2}, r_{3}^{ 3}, ..., r_{3}^{ n-1} |
***
| 1, r_{n}, r_{n}^{ 2}, r_{n}^{ 3}, ..., r_{n}^{ n-1} |
If r_{1}, r_{2}, r_{3}, ... r_{n} are all different, the matrix is nonsingular.
To prove this, we first notice that if V were singular, then there would be some nonzero column vector u = (u_{1}, u_{2}, u_{3}, ... u_{n})^{T} such that Vu is zero, i.e.,
u_{1} + u_{2}r_{1} + u_{3}r_{1}^{ 2} + ... + u_{n}r_{1}^{ n-1} = 0
u_{1} + u_{2}r_{2} + u_{3}r_{2}^{ 2} + ... + u_{n}r_{2}^{ n-1} = 0
***
u_{1} + u_{2}r_{n} + u_{3}r_{n}^{ 2} + ... + u_{n}r_{n}^{ n-1} = 0
However, this would require the polynomial p(x) = u_{1} + u_{2}x + u_{3}x^{ 2} + ... + u_{n}x^{ n-1} to have n distinct roots r_{1}, r_{2}, r_{3}, ... r_{n}, which is impossible because it is a nonzero polynomial of degree at most n-1.
In a square confluent Vandermonde matrix, some rows are accompanied by their derivatives. The same line of argument is used, but the polynomial p(x) has fewer than n distinct roots. However, it has roots whose multiplicities add up to n, which is also impossible for a nonzero polynomial of degree at most n-1.