Golden numbers are Fibonacci

This post is fourth in a series, proving the curious fact that n is a Fibonacci number if and only if one (or both) of 5n^2 + 4 or 5n^2 - 4 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 x and y are positive integers such that

y^2 - xy - x^2 = \pm 1 (**),

then (x,y) = (F_n, F_{n+1}) for some n \geq 1.

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 5x^2 \pm 4 is a perfect square, then it is a Fibonacci number.

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

y^2 + (-x)y + (-x^2 \pm 1) = 0

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

y = \frac{1}{2}(x + \sqrt{x^2 - 4(-x^2 \pm 1)}) = \frac{1}{2}(x + \sqrt{5x^2 \pm 4}).

(We want only the positive solution for y.) We now claim that if 5x^2 \pm 4 is a perfect square, then y is an integer. If 5x^2 \pm 4 is a perfect square, then it is easy to see that x + \sqrt{5x^2 \pm 4} is an integer; the only potential problem is that factor of 1/2. We can see that y will be an integer exactly when x + \sqrt{5x^2 \pm 4} is even. First, note that \sqrt{5x^2 \pm 4} will have the same parity (evenness or oddness) as x: 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 x + \sqrt{5x^2 \pm 4} 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 x is a positive integer such that 5x^2 + 4 is a perfect square, then y as defined by the above equation will also be a positive integer, such that equation (**) holds. By Lemma 2 above, this means x (and y) must be Fibonacci numbers. QED.

Proof of Lemma. The only thing we have left is to prove the lemma: if x and y are positive integers such that y^2 - xy - x^2 = \pm 1, then x and y are consecutive Fibonacci numbers.

The proof is by (strong) induction on the sum x + y. Strong induction means that in the inductive step, we get to assume that the lemma holds for all x and y with a smaller sum. With normal (weak) induction, when proving a case with x + y = n we would only get to assume the lemma for the case x + y = n-1. 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 x > y, x = y, or x < y.

  • The case x > y is actually impossible, since we would have

    y^2 - xy - x^2 < y^2 - y^2 - y^2 = -y^2

    But since y is a positive integer, -y^2 \leq -1, and so we would have y^2 - xy - x^2 < -1, which is impossible since we assumed it is equal to \pm 1.

  • Next, if x = y, then y^2 - xy - x^2 = -y^2 = \pm 1, so we must have y = 1 and hence x = 1 as well. These are consecutive Fibonacci numbers (namely, F_1 and F_2) so the lemma holds in this case.

  • The last case is x < y. Consider (a,b) = (y-x, x), which by assumption are both positive integers. It turns out that they also satisfy (**):

    \begin{array}{rcl}b^2 - ba - a^2 & = & x^2 - x(y-x) - (y-x)^2\\ &=& x^2 - xy + x^2 - y^2 + 2yx - x^2\\ &=& x^2 + xy - y^2\\ &=& -(y^2 - xy - x^2)\\ &=& \pm 1\end{array}

    Since a + b = y-x + x = y < x+y, by the inductive hypothesis we conclude that a and b are consecutive Fibonacci numbers, say (a,b) = (F_n, F_{n+1}). But then (x,y) = (b,a+b) = (F_{n+1}, F_{n+2}) 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!

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, proof and tagged , , , , , . Bookmark the permalink.

2 Responses to Golden numbers are Fibonacci

  1. Justin says:

    Is there a glossary somewhere for math terms that you use? I almost always need to start by reminding myself what a ‘lemma’ is, and it would probably be useful to have a more specific understanding of what things like theorems are.

    • Brent says:

      Not really, but I’m happy to answer questions! A theorem is a mathematical statement that has been proven, i.e. it has been logically shown why it must be true. There’s really no difference between a lemma and a theorem, other than the fact that calling something a ‘lemma’ usually indicates that we are not especially interested in it per se, but intend to use it to prove something else we do care about. In other words, a lemma is a sort of “helper theorem”.

Comments are closed.