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 5n2 – 4 or 5n2 + 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 = Fm, how can we find m?
For large m, Fm is approximately φm / √ 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 5F2 – 4 is not a perfect square. Now let’s try 5F2 + 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
The reason for this fact is straightforward to see if you invert Binet’s formula https://en.m.wikipedia.org/wiki/Fibonacci_number#Recognizing_Fibonacci_numbers
well, but the explanation given there (WP) is weird: “This formula must return an integer for all n, so the radical expression must be an integer (otherwise the logarithm does not even return a rational number).” Obviously not a mathematician but a programmer is speaking (“returns”…). But in order to get an integer, the arg of the log can NOT be an integer. And it is the half-sum of the two “almost equal” terms F*sqrt(5)=sqrt(5 F²) and sqrt(5 F² +/- 4), so if the latter IS an integer (as supposed), then the sum is irrational.
Yes, it looks like it’s missing some key information. The logarithm is base phi. Remember that phi is (sqrt(5) + 1)/2. An important thing to note about this number is that any integer power of phi is a rational linear combination of 1 and sqrt(5). For instance, phi^2 is sqrt(5)/2 + 3/2. If you know some algebra, this comes from knowing some facts about Q(sqrt(5)) (which phi is in), but it’s also not hard to see directly, by expanding it out, that phi*(a*sqrt(5) + b) is some c*sqrt(5) + d (a, b, c, d all rational).
Thus, for the log itself to be an integer, the thing inside the log must be an integer power of phi, hence some a*sqrt(5) + b, for a and b rational. If the radical expression, sqrt(5*F^2 +/- 4) is not an integer or sqrt(5), it won’t be in the above form.
Meaning there is actually a second possibility here, if 5*F^2 +/- 4 is 5 times a perfect square, the expression in the log will still be a rational linear combination of 1 and sqrt(5). However, this is quickly seen to be impossible, since 5*F^2 is divisible by 5, the expression 5*F^2 +/- 4 always has remainder 4 or 1 when divided by 5 (respectively wrt. the +/-).
This shows the “only if” direction, i.e., if the log is an integer, then 5*F^2 +/- 4 must be an integer. But what about the “if” direction? The proof is more complicated, and is shown in the PDF linked to in the original post (Gessel).
John:
You write, “For large m, Fm is approximately φ^m / √ 5.” Actually, the approximation is pretty good for small m, with an error of less than 1/4 for n=1, less than 1/5 for n=2, and less than 1/10 for n=4. As in other areas of mathematics, 5 is approximately infinity.