Fibonacci Sequence

The Fibonacci sequence is a well known and identifiable sequence. A lot has been written on its history so this is a very brief summarization and certainly is not meant to be an exhaustive description. The reader is encouraged to seek out more on the history if it’s of interest, but basically Leonardo Pisano Bigollo of Pisa, Italy, (also known as Fibonacci) asked this brain teaser in his book on mathematics called Liber Abaci, circa 1200:

If a pair of rabbits is placed in an enclosed area, how many rabbits will be born there if we assume that every month a pair of rabbits produces another pair, and that rabbits begin to bear young two months after their birth?

From this the Fibonacci sequence came to be. (Actually, the sequence was known to some in India as early as the 1100s.) It is recommended that the reader work through the solution to the brain teaser for at least the first few months.

The main focus of this article is to define mathematically the Fibonacci sequence and to explore the mathematics to generate the sequence using an elegant linear algebra approach. In particular, the following sections are presented:

Review of a Sequence

Before defining the Fibonacci sequence, it is worth reviewing the definition of a sequence. A sequence, as used here, is an ordered list of numbers where the list can be finite or infinite. Ordered simply means that the list of numbers in the sequence follows a defined rule.

Some examples of simple sequences:

  • \(\{1,2,3,4,5,6\}\) is a finite sequence containing six elements where each element is one more than the previous
  • \(\{0,1,0,1,0,1,\dots\}\) is an infinite sequence of alternating 1’s and 0’s
  • \(\{3,5,7,9,11,\dots\}\) is an infinite sequence of odd numbers beginning with 3

Each term in a sequence can be referred to by its position in the sequence. Looking at the sequence, \(\{3,5,7,9,11,\dots\}\), the first term in the sequence is 3, the second term in the sequence is 5, the third term in the sequence is 7 and so on. It is especially true in an infinite sequence that there be a way to identify any element in the sequence. Some notation is helpful: If \(x\) is used to denote an element in the sequence then \(x_{n}\) refers to the \(n^{th}\) element in the sequence (for example \(x_{4} = 9\)) and a common notation used is

\[ \left\{x_{n}\right\}_{n=1}^{\infty} \]

The rule defining the ordering (which sometimes is not very obvious) is needed to identify the \(n^{th}\) element. In the sequence, \(\{3,5,7,9,11,\dots\}\), the rule is \(x_{n} = 2n + 1\) for \(n = 1, 2, \dots, \infty\). So the \(100^{th}\) element is: \(x_{100} = 2(100) + 1 = 201\).

top

Fibonacci Sequence Defined

The Fibonacci sequence is defined as

\[ \left\{F_{n}\right\}_{n=1}^{\infty} \]

with \(F_{n}\) being the rule and defined as \(F_{n} = F_{n-1} + F_{n-2}\). The expansion of the sequence produces \(\{1,1,2,3,5,8,13\dots\}\) for \(n = 1,2,\dots,\infty\). That is, for any element in the sequence, it is computed as the sum of the two preceding elements. A sequence of this type, where the rule for a term in the sequence is a function of the previous term (or terms) in the sequence, is known as a recurrence relation. Said another way, the rule is an equation which is defined in terms of itself, hence is recursive.

Since any given element (or term) in the Fibonacci sequence is the sum of the previous two terms, initial conditions are needed to get the sequence going. One way to do this is to set the first two terms to 1. That is, by definition, \(F_{1} = 1\) and \(F_{2} = 1\) and then apply the rule for \(n = 3\) and beyond. An alternative means is to define a \(0^{th}\) term as \(F_{0} = 1\) and define \(F_{1} = 1\) and then apply the rule for \(n = 2\) and beyond.

top

The Mathematics of the Fibonacci Sequence

Given the Fibonacci sequence is defined as

\[ \left\{F_{n}\right\}_{n=1}^{\infty} \]

with \(F_{n} = F_{n-1} + F_{n-2}\) the finding of the \(n^{th}\) term in the sequence is a challenge for the sequence is a recurrence relation, which in this case means it is dependent on the two previous terms. There are several alternative ways to go about finding the \(n^{th}\) term in the sequence algorithmically. One obvious way to find \(n^{th}\) term is use brute force to compute each term in the sequence till the \(n^{th}\) term is reached. This approach is quite naive and (obviously) inefficient, especially for large values of \(n\). The approach taken here to find \(F_{n}\) is an elegant one lending itself to an efficient implementation. Consider the following equations:

\[ \begin{align} 0 \cdot F_{n-1} + 1 \cdot F_{n} &= F_{n} \\ 1 \cdot F_{n-1} + 1 \cdot F_{n} &= F_{n+1} \end{align} \]

This is a system of linear equations which can be expressed as:

\[ \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} F_{n-1} \\ F_{n} \end{bmatrix} = \begin{bmatrix} F_{n} \\ F_{n+1} \end{bmatrix} \]

To see how the \(n^{th}\) term can be found, first consider when \(n = 1\):

\[ \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} F_{0} \\ F_{1} \end{bmatrix} = \begin{bmatrix} F_{1} \\ F_{2} \end{bmatrix} \]

Next consider when \(n = 2\):

\[ \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} F_{1} \\ F_{2} \end{bmatrix} = \begin{bmatrix} F_{2} \\ F_{3} \end{bmatrix} \]

Recognize that \(\begin{bmatrix} F_{1} \\ F_{2} \end{bmatrix}\) was just found in the \(n = 1\) case and can be substituted in:

\[ \begin{align} \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} F_{1} \\ F_{2} \end{bmatrix} &= \begin{bmatrix} F_{2} \\ F_{3} \end{bmatrix} \\ \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} F_{0} \\ F_{1} \end{bmatrix} &= \begin{bmatrix} F_{2} \\ F_{3} \end{bmatrix} \\ \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{2} \begin{bmatrix} F_{0} \\ F_{1} \end{bmatrix} &= \begin{bmatrix} F_{2} \\ F_{3} \end{bmatrix} \end{align} \]

Next consider when \(n = 3\):

\[ \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} F_{2} \\ F_{3} \end{bmatrix} = \begin{bmatrix} F_{3} \\ F_{4} \end{bmatrix} \]

Again, can substitute for \(\begin{bmatrix} F_{2} \\ F_{3} \end{bmatrix}\) which was found in the \(n = 2\) case:

\[ \begin{align} \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} F_{2} \\ F_{3} \end{bmatrix} &= \begin{bmatrix} F_{3} \\ F_{4} \end{bmatrix} \\ \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{2} \begin{bmatrix} F_{0} \\ F_{1} \end{bmatrix} &= \begin{bmatrix} F_{3} \\ F_{4} \end{bmatrix} \\ \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{3} \begin{bmatrix} F_{0} \\ F_{1} \end{bmatrix} &= \begin{bmatrix} F_{3} \\ F_{4} \end{bmatrix} \end{align} \]

A pattern is beginning to form and can be generalized as:

\[ \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{n} \begin{bmatrix} F_{0} \\ F_{1} \end{bmatrix} = \begin{bmatrix} F_{n} \\ F_{n+1} \end{bmatrix} \]

To understand how to retrieve \(F_{n}\) (which is the goal) let

\[ \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{n} = \begin{bmatrix} a & b \\ c & d \end{bmatrix} \]

then

\[ \begin{bmatrix} a & b \\ c & d \end{bmatrix} \begin{bmatrix} F_{0} \\ F_{1} \end{bmatrix} = \begin{bmatrix} F_{n} \\ F_{n+1} \end{bmatrix} \]

from which the following equations result:

\[ \begin{align} a \cdot F_{0} + b \cdot F_{1} &= F_{n} \\ c \cdot F_{0} + d \cdot F_{1} &= F_{n+1} \end{align} \]

but with \(F_{0} = 0\) and \(F_{1} = 1\) (the initial conditions) this reduces to

\[ \begin{align} b &= F_{n} \\ d &= F_{n+1} \end{align} \]

Hence \(F_{n}\) is the second element of the first row of \(\begin{bmatrix} a & b \\ c & d \end{bmatrix}\), where

\[ \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{n} = \begin{bmatrix} a & b \\ c & d \end{bmatrix} \]

Thus, the finding of \(F_{n}\) is a matter of exponentiating \(\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\) to the \(n^{th}\) power and extracting the second element of the first row. For example, to find \(F_{10}\) (again, with \(F_{0} = 0\) and \(F_{1} = 1\)):

\[ \begin{align} \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{10} \begin{bmatrix} 0 \\ 1 \end{bmatrix} &= \begin{bmatrix} F_{10} \\ F_{11} \end{bmatrix} \\ \begin{bmatrix} 34 & 55 \\ 55 & 89 \end{bmatrix} \begin{bmatrix} 0 \\ 1 \end{bmatrix} &= \begin{bmatrix} F_{10} \\ F_{11} \end{bmatrix} \end{align} \]

Hence, \(F_{10} = 55\).

top

Software Implementation

Given that the Fibonacci sequence is a recurrence relation and is defined as \(F_{n} = F_{n-1} + F_{n-2}\) the finding of \(F_{n}\) can be implemented via recursive algorithmic techniques. However, the method described in The Mathematics of the Fibonacci Sequence above of the finding of \(F_{n}\) is a matter of exponentiating \(\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\) to the \(n^{th}\) power and extracting the second element of the first row. This can be done quite efficiently using matrix exponentiation. Using this approach two routines were implemented in Python making use of the numpy.linalg.matrix_power routine:

  • computeFibNum which computes the Fibonacci number for a given \(n\)
  • computeFibRange which computes the Fibonacci numbers for a sequential range of \(n\) values

For example, using computeFibNum, here is the Fibonacci number for first \(n = 10\) and then for \(n = 27\):

## Fibonacci number 10  is: 55
## Fibonacci number 27  is: 196418

Hence, \(F_{10} = 55\) (which is what was found above) and \(F_{27} = 196418\).

As an example of finding a range of Fibonnci numbers using computeFibRange, here are the the first ten numbers in the Fibonacci sequence:

Fibonacci Sequence
\(N\) Fibonacci Number
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55

And here are the Fibonacci numbers for 35 to 45:

Fibonacci Sequence
\(N\) Fibonacci Number
35 9227465
36 14930352
37 24157817
38 39088169
39 63245986
40 102334155
41 165580141
42 267914296
43 433494437
44 701408733
45 1134903170

As one can see, the Fibonacci numbers get quite large as \(n\) increases. In fact, the above routines, computeFibNum and computeFibRange, are limited to the computation of Fibonacci numbers for \(n \le 45\) for \(F_{45}\) produces the last unsigned integer. This limitation can be removed by changing the matrix \(\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\) to floating point numbers.

top

Fibonacci Spiral

A Fibonacci spiral is an interesting phenomenon. Consider placing two unit squares side-by-side. Then progressing in a counter-clockwise direction place another square with side length equal to the sum of the longest sides of the adjacent squares. That is, squares are created corresponding the numbers in the Fibonacci sequence. This process can be repeated as many times as desired. The following diagram illustrates this idea for 8 squares.

Notice that the largest square is of side length 21 which is the 8th term in the Fibonacci sequence! To create the spiral, start at the center and connect the diagonal corners with a smooth curve. The following diagram illustrates this idea for the 8 squares (colored differently for ease of visualization).

The Fibonacci spirial is one form (or approximation) of a golden spiral which is a logarithmic spiral with a growth factor of \(\phi\), the golden ratio (described in the article Description, Mathematics And Other Fun Facts of the Golden Ratio). The more Fibonacci squares added, the closer the approximation will be to a true golden spiral.

top

Fibonacci Sequence Fun Facts

Though the Fibonacci sequence is fascinating in-and-of-itself and can be found in nature and other numerous ways, here are some fun facts associated with the Fibonacci sequence:

  • Much like Pi Day is March 14th, Fibonacci Day is November 23rd, for November 23rd is 11/23 which are the first four terms in the Fibonacci sequence
  • In the TV show NUMB3RS, Fibonacci numbers were referenced by the math genius, Charlie Eppes, in the season 1 episode Sabotage in reference to the structure of crystals, spiral of galaxies and nautilus shells
  • In the TV show Criminal Minds, a serial killer used the Fibonacci sequence to define the number of victims for each killing event (season 4 episode Masterpiece). A plot of the locations of the killings are observed to follow that of a golden spiral radiating outward. From this the origin of the spiral can be computed, which hopefully would be the home of the killer.
  • In the best selling novel The Da Vinci Code by Dan Brown, the first eight numbers in the Fibonacci sequence were scrambled and left as one of the clues
  • In the classic comic strip series, Foxtrot by Bill Amend, the main charactor Jason Fox (a “10-year-old super genius fifth grader” who “Loves math, computers, and annoying his sister”) and Marcus, Jason’s “friend and partner in nerdiness”, use the Fibonacci sequence in quite a hilarious way in the October 11, 2005 comic. (Note, the sequence used in the last panel is the Perrin sequence which is defined as \(P_{n} = P_{n-2} + P_{n-3}\) with initial conditions \(P_{0} = 3\), \(P_{1} = 0\) and \(P_{2} = 2\))

  • Jason and Marcus are back at it in this February 8, 2009 Foxtrot Comic. Though there are no bad ways to eat good cheezy nachos, eating them following the Fibonacci sequence is brilliant! Thus the birth of Fibonachos! Jason and Marcus have quite the dilemma at the end with only 12 left! Hilarious!

  • Here is what Fibonachos might look like when created following the Fibonacci spiral

top