Computing Fibonacci Numbers

MA 367: Combinatorial Enumeration

Richard Hitt
Department of Mathematics and Statistics
University of South Alabama
Mobile, AL 36688

Fibonacci Growth

Perhaps one of the first mathematical models of a population growth was due to Leonardo Pisano (Fibonacci) in 1202. In this setting, we assume we have a newborn pair of rabbits who will eventually mate. We assume that rabbits are born in oppositely sexed pairs which become sexually mature at age 1 month and that the gestational term is 1 month.

Let F[n] denote the number of pairs of rabbits at the end of each month. Lets look ar different ways we can compute the number of rabbits at the end of the nth month.

Simple but Inneficient Mathematica Code for the Fibonacci Recurrence

The most natural was to describe the Fibonacci relation to Mathematica is as follows.

Note that if we want to make a table of Fibonacci numbers, this formula for F[n] is horribly inefficient. Explain why. You can use the Timing function in Mathematica to measure how long a calculation takes (in CPU seconds, not wall clock time).

Improved Code

Mathematica can be convinced to cache its previously computed information about a sequence as follows.

This approach is great if n is not too large. However, it is easy to exceed Mathematica's recursion depth if n is large. You can experiment with this approach, but you should clear Mathematica's memory of the cached F2 values if you run Timing tests so you are not using previously stored information.

Another Approach

The disadvantage in the above improvement is that in order to compute a Fibonacci number,
all the intermediate numbers are stored as rules. This will eventually require a large amount of storage for a term in the sequence if the index n is very large. In fact, for sufficiently large n, the process will fail due to exceeded capacity. Also, the lookup procedure for rules is slow. These problems can be overcome with an iterative procedure.

This procedure really flies. It does not have the recursion depth restriction of the previous procedure.

Graphs

To determine the growth rate of the Fibonacci sequence, we can plot the points.

Is this exponential? To see, we can plot the log of the data. In fact, we can let the data go further out.

Since the log plot looks linear, the data are probably exponential in growth, at least over the range we are examining. This observation is made more precise in the next subsection.

A Closed Form Method

In this subsection, we will derive the standard closed form formula for the Fibonacci sequence to show that the terms grow exponentially.

The method used to compute F3 can be rewritten in matirx form.

Now the Fibonacci sequence can be described by a matrix equation with appropriate initial conditions.

Since the eigenvectors of the matrix A are distinct, the basis can be changed to an eigenbasis (a basis consisting of distinct eigenvectors) in order to solve the system.

Under this new basis, the coupled recurrence equations become uncoupled since the coefficient matrix A is transformed into a disgonal matrix of eigenvalues.

This shows that the formula, X[n], for the nth term of the Fibonacci sequence is a linear combination of powers, say nth, of the two eigenvalues. A formula for X[n] can now be determined as follows.

This shows that a closed form formula for the nth term of the Fibonacci sequence is given by

         1   Sqrt[5] n
     (-((- - -------)  (-5 + Sqrt[5])) + 
         2      2
      
                              1 + n
         Sqrt[5] (1 + Sqrt[5])
         --------------------------) / 10
                      n
                     2

Since e1 is less than one in absolute value, the first term will go to zero as n gets large. Thus for large n, the Fibonacci sequence is approximately c2*e2^n -- exponential!

To implement this closed form description as a Mathematica definition is easy.

Notice that there is a considerable amount of algebra being done by Mathematica when using this formula to compute large terms in the sequence..

Exercise

Discuss the different methods described in this notebook for computing the terms of the Fibonacci sequence. Analyze the run times of the methods. You can use the Timing function to gather data. You can also count the number of operations required for each of the methods.