Discovering the Golden Ratio

Here’s an idea most people (like myself) would not come up with on their own. Let’s look at the sequence of ratios $\frac{F_n}{F_{n+1}}$:

$\frac{0}{1}, \frac{1}{1}, \frac{1}{2}, \frac{2}{3}, \frac{3}{5}, \frac{5}{8}, \frac{8}{13}, ...$

Simplifying, we get

$0, 1, .5, . \overline{6}, .6, .625, . \overline{615384}, ...$

We aren’t doing this just to look at the numbers; we are studying patterns between them. We should notice that the value of the ratio fluctuates as $n$ approaches infinity. As a reminder, we know that if a sequence is bounded and monotonic, it has a limit. While our sequence is bounded, it is not monotonic. We can’t yet conclude that it converges to a limit.

Let’s take a closer look at the fluctuations:

$1, -.5, .1 \overline{6}, -.0 \overline{6}, .025, -.00961538 \overline{463}, ...$

We notice the sizes of the fluctuations rapidly decreasing. In fact, the sequence of the absolute values of the fluctuations,

$1, .5, .1 \overline{6}, .0 \overline{6}, .025, .00961538 \overline{463}, ...$

is obviously$^{*}$ decreasing. Since the absolute value is bounded below by zero, that shows this sequence is Cauchy. When the successive differences between terms of a sequence approach zero, that sequence is called a Cauchy sequence. We love Cauchy sequences, because Cauchy sequences of real numbers always converge.

To reiterate: Because the sequence of ratios of successive Fibonacci numbers is a Cauchy sequence of real numbers, that sequence has a limit.

I guess we feel a little better, but we would like to find that limit. Fortunately, we derived a formula that lets us use a matrix to compute any Fibonacci number. Unfortunately, if we wanted to find $F_{2^{99}}$, we would have to do matrix multiplication $2^{99}$ times. Ain’t nobody got time for that!

Enter matrix diagonalization. A diagonal matrix is a matrix that has only zeros except down the diagonal. If a matrix is diagonal, it’s really easy to raise it to any power we like. We simply raise each diagonal element to that power.

$\begin{bmatrix} a & 0 \\ 0 & b \\ \end{bmatrix}^n = \begin{bmatrix} a^n & 0 \\ 0 & b^n \\ \end{bmatrix}$

Let’s prove it by induction.

Base case. For $n=1$,

$\begin{bmatrix} a & 0 \\ 0 & b \\ \end{bmatrix}^1 = \begin{bmatrix} a^1 & 0 \\ 0 & b^1 \\ \end{bmatrix}$

both sides simplify to the same thing, so the base case is true.

Induction step. Assume the statement is true for arbitrary $n$, and show it’s true for $n+1$.

$\begin{alignedat}{1} \begin{bmatrix} a & 0 \\ 0 & b \\ \end{bmatrix}^{n+1} &= \begin{bmatrix} a & 0 \\ 0 & b \\ \end{bmatrix} \cdot \begin{bmatrix} a & 0 \\ 0 & b \\ \end{bmatrix}^{n} \\ &= \begin{bmatrix} a & 0 \\ 0 & b \\ \end{bmatrix} \cdot \begin{bmatrix} a^n & 0 \\ 0 & b^n \\ \end{bmatrix} \\ &= \begin{bmatrix} a \cdot a^n + 0 \cdot 0 & a \cdot 0 + 0 \cdot b^n \\ 0 \cdot a^n + b \cdot 0 & 0 \cdot 0 + b \cdot b^n \\ \end{bmatrix} \\ &= \begin{bmatrix} a^{n+1} & 0 \\ 0 & b^{n+1} \\ \end{bmatrix} \\ \end{alignedat}$

There we go. Now we know for sure that raising a diagonal $2 \times 2$ matrix to an arbitrary power simply means we raise each diagonal element to that power.

So let’s try and diagonalize our friend, and let’s call our friend $A$.

$A= \begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix}$

If a matrix is diagonalizable, its diagonal entries will be that matrix’s eigenvalues.

So let’s find the eigenvalues of $A$. The eigenvalues can be determined by investigating the equation

$A \vec{x} = \lambda \vec{x}$

where $A$ is our friend, $\vec{x}$ is a vector being multiplied by $A$, and $\lambda \vec{x}$ is a scalar multiple of $\vec{x}$. The scalar multiple $\lambda$ is the eigenvalue corresponding to the eigenvector $\vec{x}$. This equation means that the matrix $A$ acts upon the vector $\vec{x}$ in such a way that the vector comes out of the matrix in the exact same direction it went in (a scalar multiple of $\vec{x}$ is a vector that lies in the same line as $\vec{x}$). This equation nicely illustrates the meaning and the relationship of those eigenthings. Eigen comes from the German word meaning own and is used to emphasize that eigenvalues and eigenvectors are inherent features of our friend. We might be getting to know this friend a little too well…

Let’s manipulate the equation by getting zero on one side and factoring out the vector $\vec{x}$

$\begin{alignedat}{1} A \vec{x} - \lambda \vec{x} &= 0 \\ (A - \lambda I)\vec{x} &= 0 \\ \end{alignedat}$

The reason for the $I$ is so that we have a properly defined matrix. Had we simply written $A - \lambda$, we would be subtracting a scalar from a matrix, which is not well-defined. What this equation now tells us is that the matrix $A - \lambda I$ maps $\vec{x}$ to the zero vector. As usual, we seek a nontrivial solution, so we assume $\vec{x}$ is nonzero. Then the equation can only be true if the matrix is not invertible, which means it’s determinant must be zero. So let’s solve the equation $\det (A - \lambda I) = 0$:

$\begin{alignedat}{1} \det (A - \lambda I) &= 0 \\ \det \bigg( \begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix} - \begin{bmatrix} \lambda & 0 \\ 0 & \lambda \\ \end{bmatrix} \bigg) &= 0 \\ \det \begin{bmatrix} - \lambda & 1 \\ 1 & 1 - \lambda \\ \end{bmatrix} &= 0 \\ - \lambda (1 - \lambda) - 1 \cdot 1 &= 0 \\ \lambda ^2 - \lambda - 1 &= 0 \\ \lambda ^2 - \lambda &= 1 \\ \lambda ^2 - \lambda + \frac{1}{4} &= 1 + \frac{1}{4} \\ \Big( \lambda - \frac{1}{2} \Big)^2 &= \frac{5}{4} \\ \lambda - \frac{1}{2} &= \pm \frac{ \sqrt{5}}{2} \\ \lambda &= \frac{1 \pm \sqrt{5} }{2} \end{alignedat}$

You might recognize this quantity as the Golden Ratio. If you’re asking, “but which one, the plus or the minus?”, the answer is both.

So, our diagonalized friend is now called $D$, and $D$ looks like

$D= \begin{bmatrix} \frac{1 + \sqrt{5} }{2} & 0 \\ 0 & \frac{1 - \sqrt{5} }{2} \\ \end{bmatrix}$

$^{*}$ It’s important to state that this sequence of decimals does not prove anything. It’s just a simple illustration of the Cauchy-ness of the sequence. To prove the sequence is Cauchy, most proofs would begin by assuming the sequence converges to the Golden Ratio, and use the fact that convergent sequences are Cauchy. But, we are trying to use the fact that this is a Cauchy sequence of real numbers in order to show convergence, before we even bother to find the limit. We can’t assume that which we are trying to prove! Here is a direct proof that the sequence is Cauchy.