Recall that a “golden number” (this is not standard terminology) is a number such that one (or both) of
or
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 are defined by
So the first few Lucas numbers are . 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:
We can prove this via straightforward induction. It’s easy to verify that the given equation holds for and
:
, and
. Now, let’s show it holds for
whenever it holds for smaller values:
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:
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 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
Now multiplying both sides of Cassini’s Identity by four and subtracting from the above equation yields
We are now left with , and all that’s left is to rearrange a bit:
.
So, as promised, we have actually proved something a bit stronger than the mere fact that every Fibonacci number is golden. If is even, then
is the square of the
th Lucas number; if
is odd, then
is.
Pingback: Golden numbers are Fibonacci | The Math Less Traveled