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:
“The world is never the same as it was.... And that’s as it should be. Every generation has the obligation to make the preceding generation irrelevant. It happens in little ways: no longer knowing the names of bands or even recognizing their sounds of music; no longer implicitly understanding life’s rules: wearing plaid Bermuda shorts to the grocery and not giving it another thought.”
—Jim Shahin (20th century)
“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)