This post is fourth in a series, proving the curious fact that is a Fibonacci number if and only if one (or both) of or is a perfect square; we call numbers of this form golden numbers. Last time, I presented Gessel’s proof that every Fibonacci number is golden. In this post, I will present Phillip James’s proof that every golden number is Fibonacci.

First, we need the following lemma:

Lemma. If and are positive integers such that

(**),

then for some .

Let’s save the proof of this until later, noting only that the above equation will come up often, so we give it the name (**) to be able to refer to it easily. First, let’s see how we can use this lemma to prove the main result.

Theorem. If is a perfect square, then it is a Fibonacci number.

Proof. Consider equation (**) again. We can think of this as a quadratic equation in , writing it as

for emphasis. We can now use the quadratic formula to solve for , obtaining

(We want only the positive solution for .) We now claim that if is a perfect square, then is an integer. If is a perfect square, then it is easy to see that is an integer; the only potential problem is that factor of . We can see that will be an integer exactly when is even. First, note that will have the same parity (evenness or oddness) as : squaring, multiplying by an odd number, adding an even number, and taking the square root of a perfect square are all operations that preserve parity. The final expression then involves adding (or subtracting) two integers of the same parity, that is, both even or both odd. This will always result in an even integer.

So, if is a positive integer such that is a perfect square, then as defined by the above equation will also be a positive integer, such that equation (**) holds. By Lemma 2 above, this means (and ) must be Fibonacci numbers. QED.

Proof of Lemma. The only thing we have left is to prove the lemma: if and are positive integers such that , then and are consecutive Fibonacci numbers.

The proof is by (strong) induction on the sum . Strong induction means that in the inductive step, we get to assume that the lemma holds for all and with a smaller sum. With normal (weak) induction, when proving a case with we would only get to assume the lemma for the case . It turns out that strong and weak induction are logically equivalent, even though strong induction seems, well, stronger. Perhaps that’s a post for another time!

We consider three cases: either , , or .

• The case is actually impossible, since we would have

  

  But since is a positive integer, , and so we would have , which is impossible since we assumed it is equal to .

• Next, if , then , so we must have and hence as well. These are consecutive Fibonacci numbers (namely, and ) so the lemma holds in this case.

• The last case is . Consider , which by assumption are both positive integers. It turns out that they also satisfy (**):

  

  Since , by the inductive hypothesis we conclude that and are consecutive Fibonacci numbers, say . But then are also consecutive Fibonacci numbers.

And that concludes the proof that all golden numbers are Fibonacci. I note that James also proves the converse of the Lemma (that is, he proves that any consecutive Fibonacci numbers satisfy equation (**)), and uses it to prove that all Fibonacci numbers are golden; you might enjoy trying to complete the proof yourself using some of the above ideas.

I’ll conclude this series with a post exploring the question of how quickly we can test an arbitrary integer for Fibonacci-ness, and in particular whether this theorem might give us a faster test than other methods. But first—Carnival of Mathematics #132 will be up soon!