How to know that a given number is Fibonacci or not?

Hi,

I am back after a long time! I am assuming the reader is well acquainted with Fibonacci numbers. Still here goes the definition:

The sequence of numbers beginning
0, 1, 1, 2, 3, 5, 8, 13...
where each successive number in the sequence is the sum of the two preceding numbers. More precisely the sequence can be defined through the recurrence relation:

F(n) = 0, if n = 0
= 1, if n = 1
= F(n-1)+F(n-2), if n > 1

Following C source code returns the n-th Fibonacci number:

int Fibonacci(int n)
{
if (n == 0 || n == 1)
return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Now, here comes my primary objective of writing this post:

How to know whether a given number belongs to Fibonacci series or not?
OR
How to know that a given number is Fibonacci or not?

Algorithm 1. (Naive approach)
Input: n
Output: true or false

// Calculate Fibonacci numbers till we reach equal to or exceed n

// Return true if we found any of the calculated numbers equal to n
// and return false otherwise

This algorithm is inefficient.

Now, here we are at the point where crux of the whole story is.

Theorem: A number n is Fibonacci if, and only if, (5*n*n + 4) OR (5*n*n - 4) is a perfect square.[Ira Gessel 1972]

Check out my next post for the proof of this theorem or google it!

Checking for perfect square is easy as follows:
1. take the square root of the number;
2a. Just check if fractional part is zero (suggested by Equinox) OR

2b. discard its fractional part;
3. take square of the integral part;
4. if this square is equal to given number then number is a perfect square or it is not.

NEXT POST: C code for above theorem and proof of the theorem.

Cheers!
Rajendra