Inverse Fibonacci numbers

As with the previous post, this post is a spinoff of a blog post by Brian Hayes. He considers the problem of determining whether a number n is a Fibonacci number and links to a paper by Gessel that gives a very simple solution: A positive integer n is a Fibonacci number if and only if either 5n² - 4 or 5n² + 4 is a perfect square.

If we know n is a Fibonacci number, how can we tell which one it is? That is, if n = F_m, how can we find m?

For large m, F_m is approximately I^m / a 5 and the error decreases exponentially with m. By taking logs, we can solve for m and round the result to the nearest integer.

We can illustrate this with SymPy. First, let's get a Fibonacci number.

 >>> from sympy import * >>> F = fibonacci(100) >>> F 354224848179261915075

Now let's forget that we know F is a Fibonacci number and test whether it is one.

 >>> sqrt(5*F**2 - 4) sqrt(627376215338105766356982006981782561278121)

Apparently 5F² - 4 is not a perfect square. Now let's try 5F² + 4.

 >>> sqrt(5*F**2 + 4) 792070839848372253127

Bingo! Now that we know it's a Fibonacci number, which one is it?

 >>> N((0.5*log(5) + log(F))/log(GoldenRatio), 10) 100.0000000

So F must be the 100th Fibonacci number.

It looks like our approximation gave an exact result, but if we ask for more precision we see that it did not.

 >>> N((0.5*log(5) + log(F))/log(GoldenRatio), 50) 99.999999999999999999999999999999999999999996687654

Related posts:

• Infinite primes via Fibonacci numbers
• Power method and Fibonacci numbers
• Fibonacci numbers and integration