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:
“What stunned me was the regular assertion that feminists were “anti-family.” . . . It was motherhood that got me into the movement in the first place. I became an activist after recognizing how excruciatingly personal the political was to me and my sons. It was the women’s movement that put self-esteem back into “just a housewife,” rescuing our intelligence from the junk pile of “instinct” and making it human, deliberate, powerful.”
—Mary Kay Blakely (20th century)
“The only phenomenon with which writing has always been concomitant is the creation of cities and empires, that is the integration of large numbers of individuals into a political system, and their grading into castes or classes.... It seems to have favored the exploitation of human beings rather than their enlightenment.”
—Claude Lévi-Strauss (b. 1908)