Lately I’ve been intrigued by the Fibonacci number sequence, i.e. the sequence where each number is the sum of the two previous. Formally the sequence is defined by the recurrence formula \(F_{n+1} = F_n+F_{n-1}\), when we set \(F_1 = 1\) and \(F_2=1\). If needed, we can use \(F_{n-1} = F_{n+1}-F_n\) to extend the sequence backwards; for instance \(F_0 = 1 – 1 = 0\).

The Fibonacci numbers have surprising connections with the golden ratio \(\phi = (1+\sqrt{5})/2\), which fulfills the equation \(\phi^2 = \phi + 1\). For example, for \(n > 0\), we have \[ \phi^n = \phi F_n + F_{n-1}. \]

This is easy to prove by induction: If \(n=1\), clearly \(\phi^1 = \phi + 0 = \phi F_1 + F_0\). Let’s assume that \(\phi^k = \phi F_k + F_{k-1}\) for some \(k > 0\). Now \[\phi^{k+1} = \phi\phi^k = \phi^2 F_k + \phi F_{k-1} = (\phi + 1)F_k + \phi F_{k-1} = \phi F_{k+1} + F_k.\]

This identity gives a formula for calculating Fibonacci multiples, somewhat similar to how De Moivre’s formula can be used to obtain formulas for sines and cosines of multiples of angles. For example, since \(\phi^{2n}\) can be written as \((\phi^n)^2\), we have \[\phi F_{2n}+F_{2n-1} = (\phi F_n + F_{n-1})^2 = \phi^2 F_n + 2\phi F_n F_{n-1} + F_{n-1}^2.\]

Substituting \(\phi+1\) for \(\phi^2\) \[\phi F_{2n}+F_{2n-1} = \phi(F_n^2+2F_nF_{n-1})+F_n^2+F_{n-1}^2.\]

Since \(\phi\) is irrational and the Fibonacci numbers are integers, this can be true only if

\begin{align}F_{2n} &= F_n^2+2F_nF_{n-1},\text{and} \\

F_{2n-1} &= F_n^2+F_{n-1}^2.\end{align}

These formulas can be used to find \(F_n\) for large \(n\) with \(\log n\) intermediate steps; ideal for solving the Fibonacci 1000000000 challenge for example. This method can also be used to prove the Fibonacci Multiples theorem directly, that is, that \(F_n\) divides \(F_{nm}\) for every \(m\).

Writing \(\phi^{nm}\) as \((\phi^n)^m\) and applying the above identity we get

\[\phi F_{nm} + F_{nm-1} = (\phi F_n + F_{n-1})^m = \sum_{k=0}^m \binom{m}{k} \phi^k F_n^k F_{n-1}^{m-k}.\]

Now let’s substitute \(\phi^k = \phi F_k + F_{k-1}\) for \(k > 0\) to obtain

\[

\phi F_{nm} + F_{nm-1} = \phi \sum_{k=1}^m \binom{m}{k} F_k F_n^k F_{n-1}^{m-k}

+ \sum_{k=1}^m \binom{m}{k} F_{k-1} F_n^k F_{n-1}^{m-k} + F_{n-1}^m.

\]

Hence

\[F_{nm} = \sum_{k=1}^m \binom{m}{k} F_k F_n^k F_{n-1}^{m-k}.\]

Now \(F_n\) divides the right hand side since it divides each of the terms of the sum. Thus \(F_n\) divides \(F_{nm}\).