## Testing Fibonacci numbers: the proofs

In my last post I stated this surprising theorem: $n$ is a Fibonacci number if and only if one of $5n^2 \pm 4$ is a perfect square.

If one of $5n^2 \pm 4$ is a perfect square, then let’s say that $n$ is a “golden number” (a nod, of course, to the close relationship of the golden ratio to the Fibonacci numbers). The theorem is an “if and only if”, so it actually says two things: first, it says that every Fibonacci number is a golden number, that is, one of $5F_k^2 \pm 4$ is always a perfect square. Second, it says that every golden number is a Fibonacci number. All together, the theorem says that “golden numbers” and Fibonacci numbers are really just two ways of looking at the same thing.

The theorem was apparently first stated and proved by Ira Gessel. His original proof lays out a very succinct argument why every Fibonacci number is golden. I like Gessel’s proof of this direction, since it actually ends up showing that the $+4$ and $-4$ alternate (as one might well have conjectured after seeing the table in my previous post), and also proving that we end up with not just any old squares, but in fact the squares of consecutive Lucas numbers (as observed by Logan Clark in a comment on my previous post). I plan to present Gessel’s proof of this direction, filling in the details of some “well-known” facts that he states without proof. (Well-known to his readers, perhaps, but not necessarily to mine!)

For the other direction—that every golden number is Fibonacci—Gessel actually gives two proofs, but both use some relatively high-powered number theory machinery—and as it turns out, the high-powered machinery is unnecessary. More recently, Phillip James published a much more elementary proof of the theorem. One nice thing about James’s proof is that it uses a common framework to prove both directions. I still prefer Gessel’s proof of the first direction, since it provides more insight about the relationship to Lucas numbers, but for the other direction I plan to present James’s proof that every golden number is Fibonacci, which is much easier to understand than Gessel’s. (If enough folks are interested, though, I could perhaps present Gessel’s proofs as well; they are certainly interesting!) 