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 $k$ th Lucas number; if $k$ is odd, then $5F_k^2 - 4$ is.

About Brent

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

View all posts by Brent →