Fibonacci numbers are golden

Recall that a “golden number” (this is not standard terminology) is a number n such that one (or both) of 5n^2 + 4 or 5n^2 - 4 is a perfect square. In this post, I’ll explain Gessel’s proof that every Fibonacci number is golden. First, we need two lemmas.

The Lucas numbers L_k are defined by

\begin{array}{rcl}L_0 & = & 2 \\ L_1 & = & 1 \\ L_n & = & L_{n-1} + L_{n-2} \quad (n \geq 2). \end{array}

So the first few Lucas numbers are 2, 1, 3, 4, 7, 11, 18, 29, 47\dots. They have exactly the same defining recursion as the Fibonacci numbers; only the initial conditions are different. So it should come as no particular surprise that they have many close relationships with the Fibonacci numbers. Here’s one such relationship, which is our first lemma:

Lemma 1: L_k = F_{k+1} + F_{k-1} \qquad (k \geq 1).

We can prove this via straightforward induction. It’s easy to verify that the given equation holds for k = 1 and 2: L_1 = 1 = 1 + 0 = F_2 + F_0, and L_2 = 3 = 2 + 1 = F_3 + F_1. Now, let’s show it holds for k + 1 whenever it holds for smaller values:

\begin{array}{rcl}L_{k+1} & = & L_k + L_{k-1} \\ & = & F_{k+1} + F_{k-1} + F_k + F_{k-2} \\ & = & F_{k+2} + F_k\end{array}

The first equality is from the definition of Lucas numbers; the second equality is the induction hypothesis; and the third just applies the Fibonacci definition twice.

The second lemma we need is called Cassini’s Identity:

Lemma 2: (-1)^k + F_k^2 = F_{k+1}F_{k-1} \qquad (k \geq 1).

I actually proved this by induction in a post from five years ago, so instead of reproducing the proof here, I’ll just direct you to that post! There is also a nice proof using determinants of 2\times 2 matrices, due to Knuth, and a bijective proof due to Werman and Zeilberger. This page on cut-the-knot.org collects a bunch of different proofs, including the ones mentioned above.

Now, squaring both sides of Lemma 1 gives us

L_k^2 = F_{k+1}^2 + 2F_{k+1}F_{k-1} + F_{k-1}^2.

Now multiplying both sides of Cassini’s Identity by four and subtracting from the above equation yields

\begin{array}{rcl}L_k^2 - 4(-1)^k - 4F_k^2 & = & F_{k+1}^2 + 2F_{k+1}F_{k-1} + F_{k-1}^2 - 4F_{k+1}F_{k-1} \\ & = & F_{k+1}^2 - 2F_{k+1}F_{k-1} + F_{k-1}^2 \\ & = & (F_{k+1} - F_{k-1})^2 \\ & = & F_k^2.\end{array}

We are now left with L_k^2 - 4(-1)^k - 4F_k^2 = F_k^2, and all that’s left is to rearrange a bit:

5F_k^2 + 4(-1)^k = L_k^2.

So, as promised, we have actually proved something a bit stronger than the mere fact that every Fibonacci number is golden. If k is even, then 5F_k^2 + 4 is the square of the kth Lucas number; if k is odd, then 5F_k^2 - 4 is.

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.

One Response to Fibonacci numbers are golden

  1. Pingback: Golden numbers are Fibonacci | The Math Less Traveled

Comments are closed.