The Fibonacci Code

| 0 Comments

Last time[1] we took a first look into the implementation of sequences and series, being ordered lists of terms defined by their positions and the partial sums of those terms respectively. Specifically, if we have a sequence of terms \(s_i\) then its associated series contains the terms \(S_n\) given by
\[ S_n = \sum_{i=1}^n s_i \]
where \(\sum\) is the summation sign.

Whilst the implementations of arithmetic and geometric sequences and their associated series were somewhat subtle, they're not particularly interesting from a mathematical perspective and so this time we'll take a look at something a little more complicated.

The Fibonacci Sequence

I rather suspect that every introduction to mathematical sequences will turn to the Fibonacci sequence before too long. It can be defined with the rules
\[ \begin{align*} s_0 &= 0\\ s_1 &= 1\\ s_n &= s_{n-1} + s_{n-2} \end{align*} \]
for \(n\) greater than one, yielding the sequence
\[ \begin{align*} s_0 &= 0\\ s_1 &= 1\\ s_2 &= 1\\ s_3 &= 2\\ s_4 &= 3\\ s_5 &= 5\\ s_6 &= 8\\ \vdots \end{align*} \]
From a programmer's perspective it's typically used as an introduction to recursion with something like

Listing 1: A Recursive Implementation Of The Fibonacci Sequence
function fibonacciSequence(i) {
 if(i!==ak.floor(i) || i<0) {
  throw new Error('invalid index');
 }

 if(i===0) return 0;
 if(i===1) return 1;
 return fibonacciSequence(i-1) + fibonacciSequence(i-2);
}

Whilst this certainly works, as illustrated by program 1, it's hideously inefficient, as illustrated by program 1.

Program 1: Recursive Fibonacci

The problem here is that we're calling the function with the same arguments over and over again. For example

fibonnaciSequence(5) = fibonnaciSequence(4) + fibonnaciSequence(3)

                     = fibonnaciSequence(3) + fibonnaciSequence(2)
                     + fibonnaciSequence(2) + fibonnaciSequence(1)

                     = fibonnaciSequence(2) + fibonnaciSequence(1)
                     + fibonnaciSequence(1) + fibonnaciSequence(0)
                     + fibonnaciSequence(1) + fibonnaciSequence(0)
                     + fibonnaciSequence(1)

                     = fibonnaciSequence(1) + fibonnaciSequence(0)
                     + fibonnaciSequence(1)
                     + fibonnaciSequence(1)
                     + fibonnaciSequence(0)
                     + fibonnaciSequence(1)
                     + fibonnaciSequence(0)
                     + fibonnaciSequence(1)
A typical way to address such problems is to keep a cache of previously requested terms so that we don't go to the trouble of calculating them more than once, a technique known as memoization. Listing 2 shows how we might do this for the Fibonacci sequence.

Listing 2: A Memoized Implementation Of The Fibonacci Sequence
var cache = [0, 1];

function fibonacciSequence(i) {
 if(i!==ak.floor(i) || i<0) {
  throw new Error('invalid index');
 }

 if(ak.nativeType(cache[i])!==ak.NUMBER_T) {
  cache[i] = fibonacciSequence(i-1)
           + fibonacciSequence(i-2);
 }
 return cache[i];
}

This is significantly faster than our first implementation, as demonstrated by program 2.

Program 2: Memoized Fibonacci

Of course this does add a certain memory overhead, but that's a trade-off that we're frequently willing to make.

Although not, as it happens, in this case...

Doing Away With Recursion Altogether

One of the rather surprising facts about the Fibonacci sequence is that it is possible to calculate each of its terms without reference to any of its previous terms using the formula
\[ \begin{align*} \phi &= \frac{1 + \sqrt{5}}{2} \approx \phantom{-} 1.618034\\ \phi^\prime &= \frac{1 - \sqrt{5}}{2} \approx -0.618034\\ s_n &= \frac{\phi^n - {\phi^\prime}^n}{\sqrt{5}} \end{align*} \]
as proven by derivation 1.

Derivation 1: Direct Evaluation Of The Terms
Firstly, let's rearrange the recurrence relation into
\[ s_n - s_{n-1} - s_{n-2} = 0 \]
Next, let us replace \(s_n\) with \(x^n\) to yield
\[ x^n - x^{n-1} - x^{n-2} = 0 \]
Finally, if we divide this by \(x^{n-2}\), we get
\[ x^2 - x - 1 = 0 \]
Now this is simply a quadratic equation of the form \(ax^2+bx+c=0\), which is easily solved with the formula that we learned in school
\[ x = \frac{-b \pm \sqrt{b^2-4ac}}{2a} = \frac{1 \pm \sqrt{5}}{2} \]
If we define
\[ \phi = \frac{1 + \sqrt{5}}{2}, \; \phi^\prime = \frac{1 - \sqrt{5}}{2} \]
then the recurrence relation must be satisfied by terms of the form
\[ s_n = A \times \phi^n + B \times {\phi^\prime}^n \]
for some \(A\) and \(B\), since
\[ \begin{align*} s_n - s_{n-1} - s_{n-2} &= \left(A \times \phi^n + B \times {\phi^\prime}^n\right) - \left(A \times \phi^{n-1} + B \times {\phi^\prime}^{n-1}\right) - \left(A \times \phi^{n-2} + B \times {\phi^\prime}^{n-2}\right)\\ &= A \times \phi^{n-2} \times \left(\phi^2 - \phi - 1\right) + B \times {\phi^\prime}^{n-2} \times \left({\phi^\prime}^2 - \phi^\prime - 1\right)\\ &= A \times \phi^{n-2} \times 0 + B \times {\phi^\prime}^{n-2} \times 0 = 0 \end{align*} \]
Since \(s_0\) equals zero, we must have \(A+B\) equal to zero and so
\[ s_n = A \times \phi^n - A \times {\phi^\prime}^n = A \times \left(\phi^n - {\phi^\prime}^n\right) \]
Furthermore, since \(s_1\) equals one we must also have
\[ s_1 = A \times \left(\phi - {\phi^\prime}\right) = A \times \sqrt{5} = 1 \]
and so
\[ s_n = \frac{\phi^n - {\phi^\prime}^n}{\sqrt{5}} \]

Note that the constants \(\phi\) and \(\phi^\prime\) are related to each other with
\[ \begin{align*} \phi + \phi^\prime &= \frac{1 + \sqrt{5}}{2} + \frac{1 - \sqrt{5}}{2} = \frac{1 + \sqrt{5} + 1 - \sqrt{5}}{2} = \frac{2}{2} = 1\\ \phi \times \phi^\prime &= \frac{1 + \sqrt{5}}{2} \times \frac{1 - \sqrt{5}}{2} = \frac{\left(1 + \sqrt{5}\right) \times \left(1 - \sqrt{5}\right)}{4} = \frac{1 - \sqrt{5} + \sqrt{5} - 5}{4} = -\frac{4}{4} = -1 \end{align*} \]
and so
\[ \begin{align*} \phi^\prime &= 1-\phi = -\frac{1}{\phi}\\ s_n &= \frac{\phi^n - (1-\phi)^n}{\sqrt{5}} = \frac{\phi^n - (-\phi)^{-n}}{\sqrt{5}} \end{align*} \]
It was in anticipation of this that I included the constant ak.PHI in AK.js way back in the very first post[2] and program 3 uses it to implement the directly evaluated Fibonacci sequence.

Program 3: Direct Fibonacci

Well, that's embarrassing; I forgot to take floating point rounding errors into account! At least the nearest integers to the results are the terms of the Fibonacci sequence, so if we round them we should be set.

Hmmm...

Now it's clearly the case that the square root of five is greater than two and so its reciprocal is less than one half. Furthermore, the absolute value of \(1-\phi\) is less than one and hence it must also be the case that
\[ \frac{(1-\phi)^n}{\sqrt{5}} < \frac{1}{2} \]
for all non-negative integer \(n\).
So if we're going to have to round the results of the formula to the nearest integer anyway, we might as well ignore the powers of \(1-\phi\) in the top of the fraction!

Listing 3 gives the implementation of ak.fibonacciSequence which does just that.

Listing 3: ak.fibonacciSequence
var MUL = 1/Math.sqrt(5);

ak.fibonacciSequence = function(i) {
 if(i!==ak.floor(i) || i<0) {
  throw new Error('invalid index in ak.fibonacciSequence');
 }
 return ak.round(Math.pow(ak.PHI, i)*MUL);
};

This can be found in FibonacciSequence.js and program 4 demonstrates that it does indeed yield the terms of the Fibonacci sequence.

Program 4: ak.fibonacciSequence

The Fibonacci Series?!

Derivation 2: The Fibonacci Series
Firstly, by the definition of a series, we have
\[ S_n - S_{n-1} = s_n \]
Next, by the definition of the Fibonacci sequence, we have
\[ s_{n+2} - s_{n+1} = \left(s_{n+1} + s_n\right) - s_{n+1} = s_n \]
If this is to hold for all indices then it must be the case that
\[ S_n = s_{n+2} + c \]
for some constant \(c\) and, given that
\[ S_0 = 0, \; s_2 = 1 \]
it must be equal to minus one.
I think that it's fair to say that there's not that much attention given to the series associated with the Fibonacci sequence. Nevertheless, I think that it's worthy of consideration, if for nothing but completeness' sake.

It turns out that each term of the Fibonacci series \(S_n\) can be found from the \((n+2)^\mathrm{th}\) term of the Fibonacci sequence with
\[ S_n = s_{n+2} - 1 \]
as proven by derivation 2.

Now I must admit that the fact that the Fibonacci sequence and series are so intimately related came as something of a surprise to me, but it certainly makes the implementation of the latter a doddle, as illustrated by the ak.fibonacciSeries function given in listing 4 and defined in FibonacciSeries.js.

Listing 4: ak.fibonacciSeries
var MUL = 1/Math.sqrt(5);

ak.fibonacciSeries = function(i) {
 if(i!==ak.floor(i) || i<0) {
  throw new Error('invalid index in ak.fibonacciSeries');
 }
 return ak.round(Math.pow(ak.PHI, i+2)*MUL)-1;
};

Program 5 demonstrates that this is correct by showing that the differences between subsequent terms are the terms of the Fibonacci sequence.

Program 5: ak.fibonacciSeries

Some Properties Of The Fibonacci Sequence

Perhaps the most famous property of the Fibonacci sequence is that the ratio of its consecutive terms
\[ \frac{s_{n+1}}{s_n} = \frac{\frac{\phi^{n+1} - (1-\phi)^{n+1}}{\sqrt{5}}}{\frac{\phi^n - (1-\phi)^n}{\sqrt{5}}} = \frac{\phi^{n+1} - (1-\phi)^{n+1}}{\phi^n - (1-\phi)^n} \]
tends to \(\phi\) as \(n\) tends to infinity, as demonstrated by program 6.

Program 6: Ratios Of Consecutive Terms

This follows trivially from the fact that the absolute value of \(1-\phi\) is less than one and so
\[ \lim_{n \to \infty} (1-\phi)^n = 0 \]
meaning that
\[ \lim_{n \to \infty} \frac{s_{n+1}}{s_n} = \lim_{n \to \infty} \frac{\phi^{n+1} - (1-\phi)^{n+1}}{\phi^n - (1-\phi)^n} = \lim_{n \to \infty} \frac{\phi^{n+1} - 0}{\phi^n - 0} = \lim_{n \to \infty} \phi = \phi \]
Note that this is also true of the Fibonacci series, for much the same reason.

We can also represent the rules of the Fibonacci sequence using matrices with
\[ \begin{pmatrix} s_{n+1} & s_n\\ s_n & s_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}^n \]
for \(n\) greater than zero, since
\[ \begin{pmatrix} s_2 & s_1\\ s_1 & s_0 \end{pmatrix} = \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}^1 \]
and, by the rules of matrix arithmetic
\[ \begin{align*} \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}^n &= \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix} \times \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}^{n-1} = \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix} \times \begin{pmatrix} s_n & s_{n-1}\\ s_{n-1} & s_{n-2} \end{pmatrix} \\ &= \begin{pmatrix} s_n + s_{n-1} & s_{n-1} + s_{n-2}\\ s_n & s_{n-1} \end{pmatrix} = \begin{pmatrix} s_{n+1} & s_n\\ s_n & s_{n-1} \end{pmatrix} \end{align*} \]
for \(n\) greater than one.

Derivation 3: Fibonacci Meets Pythagoras
Firstly, by the rules of matrix arithmetic, we have
\[ \mathbf{M}^{2n} = \mathbf{M}^{n} \times \mathbf{M}^{n} \]
and so
\[ \begin{pmatrix} s_{2n+1} & s_{2n}\\ s_{2n} & s_{2n-1} \end{pmatrix} = \begin{pmatrix} s_{n+1} & s_n\\ s_n & s_{n-1} \end{pmatrix} \times \begin{pmatrix} s_{n+1} & s_n\\ s_n & s_{n-1} \end{pmatrix} \\ \quad= \begin{pmatrix} s_{n+1}^2 + s_n^2 & s_{n+1} \times s_n + s_n \times s_{n-1}\\ s_{n+1} \times s_n + s_n \times s_{n-1} & s_n^2 + s_{n-1}^2 \end{pmatrix} \]
yielding the identities
\[ \begin{align*} s_{2n} &= s_n \times \left(s_{n+1} + s_{n-1}\right)\\ s_{2n-1} &= s_n^2 + s_{n-1}^2 \end{align*} \]
From the second of these we have
\[ \begin{align*} s_{2n-1}^2 &= \left(s_n^2 + s_{n-1}^2\right)^2\\ &= s_n^4 + 2 \times s_n^2 \times s_{n-1}^2 + s_{n-1}^4\\ &= s_n^4 - 2 \times s_n^2 \times s_{n-1}^2 + s_{n-1}^4 + 4 \times s_n^2 \times s_{n-1}^2\\ &= \left(s_n^2 - s_{n-1}^2\right)^2 + \left(2 \times s_n \times s_{n-1}\right)^2 \end{align*} \]
This might seem to be of little more than academic interest, but it does reveal a rather surprising relationship between the Fibonacci sequence and Pythagorean triangles, being right angled triangles whose sides all have integer lengths. Specifically, if we define
\[ \begin{align*} a & = s_n^2 - s_{n-1}^2\\ b & = 2 \times s_n \times s_{n-1}\\ c &= s_{2n-1} \end{align*} \]
then we have
\[ a^2+b^2=c^2 \]
as proven in derivation 3. Consequently, by Pythagoras's theorem, there must be a right-angled triangle having a hypotenuse of length \(c\) and two other sides of lengths \(a\) and \(b\). Well, at least when none of those values are equal to zero, which is true when \(n\) is greater than two.

In fact, we can derive all sorts of properties of the Fibonacci sequence from this matrix representation. For example, from the determinant
\[ \begin{vmatrix} s_{n+1} & s_n\\ s_n & s_{n-1} \end{vmatrix} = \begin{vmatrix} 1 & 1\\ 1 & 0 \end{vmatrix}^n \]
we get Cassini's identity
\[ s_{n+1} \times s_{n-1} - s_n^2 = (-1)^n \]
For another, the eigenvalues of the initial matrix are \(\phi\) and \(1-\phi\), as shown (at least to within numerical approximation error) by program 7 using our ak.jacobiDecomposition class[3].

Program 7: Fibonacci Meets Jacobi

Unfortunately, there's not a hope in hell that you'll be able to use any of them to unlock some Parisian safe containing evidence of a secret that would bring down the Catholic church but, hey, they're pretty interesting nevertheless.

Amen.

References

[1] A Sequence Of Predictable Events, www.thusspakeak.com, 2016.

[2] Climbing Mount Impractical, www.thusspakeak.com, 2013.

[3] Conquering The Eigen, www.thusspakeak.com, 2014.

Leave a comment