From a recent post on Brian Hayes’ blog, bit-player, I learned the following curious fact:
is a Fibonacci number if and only if either or is a perfect square.
Recall that the Fibonacci numbers begin where each number is the sum of the previous two. So we can check that, for example,
are all perfect squares. Or, we could ask whether is a Fibonacci number? Well, just compute , which yields and . The former is a perfect square (namely, ), so is a Fibonacci number! (In fact, it is .)
Well, OK, so maybe that’s not really all that practical. It turns out that despite first appearances, I don’t think it even really gives you a fast way to test whether a number is Fibonacci (…in case you wanted that for some reason)—there are more straightforward algorithms that are just as fast. Yes, the formula is simple, but we need to think about questions like: how efficiently can you test a (large) integer to see if it is a perfect square? I’ll get back to that in a future post.
But in any case, whether or not it turns out to be computationally practical, I just think it’s cool that there is such a simple characterization of Fibonacci numbers, and perhaps surprising that Fibonacci numbers have anything to do with perfect squares. Over the next few posts I plan to go carefully through a proof, and then tackle the question of how quickly we can test whether a given number is a Fibonacci number.
In the meantime, I’ll let you study the above examples, try some of your own, and make some conjectures: will the always alternate? And what can we say about the sequence of perfect squares , , , , , and so on?