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?

About Brent

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

View all posts by Brent →

8 Responses to Testing Fibonacci numbers

Christophe says:

February 27, 2016 at 7:15 am

Thanks of sharing this !

An advantage of this criterion is that it covers only integers.
Logan Clark says:

February 27, 2016 at 3:15 pm

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.
- Brent says:
  
  February 27, 2016 at 3:24 pm
  
  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
obryant says:

March 7, 2016 at 2:08 pm

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.
- Brent says:
  
  March 7, 2016 at 8:58 pm
  
  Indeed, nice observation!
Hyman Mohmand says:

March 11, 2016 at 10:59 pm

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.
Daniel Forgues says:

April 8, 2016 at 4:03 pm

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