The Fibonacci numbers form a sequence , where , , and for .
I. Show ratios of consecutive Fibonacci numbers converge. Derive their limit .
i) Rearrange the recurrence equation to resemble the first convergent in a simple continued fraction.
Define and for let:
ii) Construct the continued fraction for a few terms, observing that the sequence of convergents form the Fibonacci ratios.
Continuing with , ,…, one constructs a simple infinite continued fraction consisting of all 1’s. It is known that any infinite continued fraction uniquely represents an irrational number, and the sequence of convergents has this number as a limit, with alternate terms forming two subsequences that converge from above and below (see Problem 3 solution).
iii)Deduce the infinite fraction’s closed form quadratic equation, which can then be solved for real roots and .
With proof of convergence given, let ; then one obtains . Rewriting this quadratic polynomial as one obtains the positive root as the desired limit value:
is called the Golden Mean; the other root is .
II): Derive a closed-form solution for the nth Fibonacci number.
i) Observe the interesting relations for :
Verify by induction. For case , is immediately true. Assume it is true for . Then using and rewriting in terms of and from the recursion equation,
With the equation proved via the same mechanism, these equations are verified.
ii) Combine these equations (i) to remove the term and express in terms of and .
That’s one of the great integer disguises, don’t you think?
iii) Alternatively, one can write simultaneous linear equations to express the numerators and denominators in the sequence of ratios above, then use linear algebra.
Write the nth fractional convergent in terms of distinct variables: .
Then , giving
In matrix form:
Thus to go from one convergent to the next in sequence involves multiplication by a matrix, and this can be repeated times to express the nth convergent in terms of the initial values :
Call our matrix F. Surprise, the characteristic polynomial of is ; solving it gives the eigenvalues and and eigenvectors and .
Diagonalize via , so that , where
, , , .
There it is again, the Binet Formula: .