Fibonacci Numbers - Recognizing Fibonacci Numbers

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.