Recognizing Fibonacci Numbers
The question may arise whether a positive integer z is a Fibonacci number. Since is the closest integer to, the most straightforward, brute-force test is the identity
which is true if and only if z is a Fibonacci number. In this formula, can be computed rapidly using any of the previously discussed closed-form expressions.
One implication of the above expression is this: if it is known that a number z is a Fibonacci number, we may determine an n such that F(n) = z by the following:
Alternatively, a positive integer z is a Fibonacci number if and only if one of or is a perfect square.
A slightly more sophisticated test uses the fact that the convergents of the continued fraction representation of are ratios of successive Fibonacci numbers. That is, the inequality
(with coprime positive integers p, q) is true if and only if p and q are successive Fibonacci numbers. From this one derives the criterion that z is a Fibonacci number if and only if the closed interval
contains a positive integer. For, it is easy to show that this interval contains at most one integer, and in the event that z is a Fibonacci number, the contained integer is equal to the next successive Fibonacci number after z. Somewhat remarkably, this result still holds for the case, but it must be stated carefully since appears twice in the Fibonacci sequence, and thus has two distinct successors.
Read more about this topic: Fibonacci Numbers
Famous quotes containing the words recognizing and/or numbers:
“By recognizing a favorable opinion of yourself, and taking pleasure in it, you in a measure give yourself and your peace of mind into the keeping of another, of whose attitude you can never be certain. You have a new source of doubt and apprehension.”
—Charles Horton Cooley (1864–1929)
“Think of the earth as a living organism that is being attacked by billions of bacteria whose numbers double every forty years. Either the host dies, or the virus dies, or both die.”
—Gore Vidal (b. 1925)