Testing Fibonacci numbers

From a recent post on Brian Hayes’ blog, bit-player, I learned the following curious fact:

n is a Fibonacci number if and only if either 5n^2 + 4 or 5n^2 -  4 is a perfect square.

Recall that the Fibonacci numbers begin 0, 1, 1, 2, 3, 5, 8, \dots where each number is the sum of the previous two. So we can check that, for example,

\begin{array}{rclcl} 5 \cdot 0^2 + 4 & = & 4 & = & 2^2 \\ 5 \cdot 1^2 - 4 & = & 1 & = & 1^2 \\ 5 \cdot 1^2 + 4 & = & 9 & = & 3^2 \\ 5 \cdot 2^2 - 4 & = & 16 & = & 4^2 \\ 5 \cdot 3^2 + 4 & = & 49 & = & 7^2 \\ 5 \cdot 5^2 - 4 & = & 121 & = & 11^2 \\ 5 \cdot 8^2 + 4 & = & 324 & = & 18^2 \end{array}

are all perfect squares. Or, we could ask whether 102334155 is a Fibonacci number? Well, just compute 5 \cdot 102334155^2 \pm 4, which yields 52361396397820129 and 52361396397820121. The former is a perfect square (namely, 228826127^2), so 102334155 is a Fibonacci number! (In fact, it is F_{40}.)

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 \pm 4 always alternate? And what can we say about the sequence of perfect squares 2^2, 1^2, 3^2, 4^2, 7^2, and so on?

Advertisements

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in arithmetic, computation, famous numbers, fibonacci and tagged , , , . Bookmark the permalink.

8 Responses to Testing Fibonacci numbers

  1. Christophe says:

    Thanks of sharing this !

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

  2. Logan Clark says:

    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.

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

  4. obryant says:

    Say you need to know if there is a fibonacci number that is a perfect cube. Suppose F_n = x^3, and then 5x^6 \pm 4 = y^2 for some integer y. The original problem has been changed: are there integers (x,y) such that 5x^6+4=y^2 or 5x^6-4 = y^2. 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.

  5. 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.

  6. Daniel Forgues says:

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

Comments are closed.