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 Number
Famous quotes containing the words recognizing and/or numbers:
“Conscience was the barmaid of the Victorian soul. Recognizing that human beings were fallible and that their failings, though regrettable, must be humoured, conscience would permit, rather ungraciously perhaps, the indulgence of a number of carefully selected desires.”
—C.E.M. (Cyril Edwin Mitchinson)
“What culture lacks is the taste for anonymous, innumerable germination. Culture is smitten with counting and measuring; it feels out of place and uncomfortable with the innumerable; its efforts tend, on the contrary, to limit the numbers in all domains; it tries to count on its fingers.”
—Jean Dubuffet (1901–1985)