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?

##
About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

Thanks of sharing this !

An advantage of this criterion is that it covers only integers.

2+1=3, 3+1=4, 4+3=7, 7+4=11, 11+7=18, etc.

I can’t remember the name of this type of sequence though.

Right you are! As for the name, try searching on the OEIS: https://oeis.org/ .

Pingback: Testing Fibonacci numbers: the proofs | The Math Less Traveled

Say you need to know if there is a fibonacci number that is a perfect cube. Suppose , and then for some integer y. The original problem has been changed: are there integers such that or . We have succeeded in removing “Fibonacci” from the statement of the problem, and just have a (difficult) diophantine equation now. That may or may not be helpful, but it is certainly interesting.

Indeed, nice observation!

This is not the most efficient algorithm to check whether a given number is a Fibonacci number. Matrix exponentiation is much faster than this method.

The sequence of perfect squares you get are the squares of Lucas numbers: A001254 on OEIS.