Four ways to Fibonacci

June 2, 2022. The Fibonacci numbers arise frequently (and often unexpectedly) in mathematics and in biological systems. In this post, we discuss four ways of calculating them: through brute force, through brute force (but in a more clever fashion), through linear algebra, and finally through the use of generating functions.

The Fibonacci numbers are a sequence of integers defined recursively by \(f_0 = 0, f_1 = 1\), and

\begin{equation}\label{eq:fibonacci} f_n = f_{n-1} + f_{n-2} \end{equation}

for \(n > 1\). If one has a computer on hand, this immediately invites a brute force recursive solution.

Method 1: Brute force computation

Translating the definition of the Fibonacci numbers in Eq. \eqref{eq:fibonacci} directly into code (in this case, Python), we end up with:

1
2
3
4
5
6
7
 
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)
 

This solution is conceptually pretty as it makes evident use of the recursive structure of the numbers, but in practice performs very poorly. For one, Python has a recursion limit of 1000 by default and we should probably use a functional programming language (such as Haskell) instead which is better suited for handling recursion. However even beyond this technical limitation, as the input \(n\) grows large the above method slows down considerably. Let us calculate how many operations are required to calculate the \(n\)th fibonacci number with the above algorithm. Let us make the ansatz that the the number of addition operations \(A(n)\) required to produce the \(n\)th fibonacci number is \(A(n) = x^n\) (for some \(x > 1\)). By the defining recursive formula of Eq. \eqref{eq:fibonacci}, we have (for \(n > 1\)) that:

and so with our ansatz this becomes:

Dividing out by \(x^{n-2}\) and rearranging, we find:

Since we are interested in the asymptotic (large \(n\)) number of additions required to calculate \(f_n\), we have in this limit that \(x^{2 - n} \to 0\) and hence:

Applying the quadratic formula to solve for \(x\), we find:

and taking the positive solution, we find that \(x\) is precisely the golden ratio:

and so we conclude:

We will see very shortly that the golden ratio will come up when we solve for a closed-form expression for \(f_n\). Before we try to find this, let us see if we can improve the above brute force algorithm (as the exponential time complexity we find above is quite terrible in practice). The inefficiency comes from the fact that we do a lot of redundant computations between the two branches of the recursive calls to fibonacci(n). If we had some way to “remember” the computations we have already done, we could avoid this redundancy. To this end, we introduce memoization, where we store the results of past calls to the function and return them when they are again requested (instead of computing them all over again).

Method 2: Brute force computation (with memoization)

Our improved algorithm takes the form:

1
2
3
4
5
6
7
 
fib_dict = {}
fib_dict[0] = 0
fib_dict[1] = 1
def fibonacci_mem(n):
    if n not in fib_dict:
        fib_dict[n] = fibonacci_mem(n-1) + fibonacci_mem(n-2)
    return fib_dict[n]   
 

where we have defined a dictionary fib_dict that stores computed fibonacci numbers so we don’t have to compute them all over again. Since checking if a key is in a dictionary and dictionary lookup are both \(O(1)\) on average, this memoized algorithm is actually linear in time complexity, instead of exponential.

Let us verify this claim that \(T(n) = O(n)\) where \(T(n)\) is the time complexity of calculating the \(n\)th Fibonacci number with the above improved algorithm. First, we have that \(T(0) = T(1) = O(1)\). For \(n > 1\), the time complexity \(T(n)\) is equal (from Eq. \eqref{eq:fibonacci}) to the time complexity of calculating \(f_{n-1}\) plus the time complexity of calculating \(f_{n-2}\) plus an \(O(1)\) addition operation of adding them together. Computing \(f_{n-1}\) will be a \(T(n-1)\) operation, but since the computation of \(f_{n-2}\) will already be done (and recorded) in the computation of \(f_{n-1}\), this will just be an \(O(1)\) dictionary lookup. Hence:

Now recursively applying this formula \(n-1\) times, we find:

which proves the claim. Memoization is in general improvement for problems with recursive structure. Having explored the problem fairly thoroughly algorithmically, let us see if we can find insights through mathematical derivation.

Method 3: Linear algebra and diagonalization

In this next approach, we will use some techniques from linear algebra to obtain a closed form expression for the Fibonacci numbers. To start, we make the observation that we can write the recursion relation of Eq. \eqref{eq:fibonacci} as a matrix equation:

where:

By recursive application of this formula, we can write the LHS in terms of \(f_1 = 1\) and \(f_0 = 0\):

If we can obtain a closed form expression for \(A^{n-1}\), we can easily evaluate the left hand side of the above equation to find \(f_n\). To do this, we diagonalize \(A\). Solving for the eigenvalues of \(A\), we have:

Applying the quadratic formula, we find that \(\lambda_1 = \frac{1 + \sqrt{5}}{2}\), \(\lambda_2 = \frac{1 - \sqrt{5}}{2}\). Note that the golden ratio again emerges here, and we may write \(\lambda_1 = \varphi\), \(\lambda_2 = 1 - \varphi\). Solving for the corresponding eigenvectors, we have:

If we then let:

we can diagonalize \(A\) as:

where \(V^{-1}\) is obtained by inverting \(V\):

Powers of \(A\) can be easily obtained in this form:

where

Therefore by matrix-vector multiplication we have:

from which we conclude the closed form solution of \(f_n\) to be:

In the limit of large \(n\), since \(1 - \varphi < 0\) we have \((1 - \varphi)^n \to 0\). In this limit we therefore have:

A notable observation is that the value of \(f_n\) has the same asymptotic growth as the time complexity/number of operations required to calculate it per the brute force algorithmic approach!

Method 4: Generating functions

For a final approach, we introduce the notion of a generating function, where an infinite sequence of numbers is encoded in the coefficients of a power series. A common application of generating functions is in probability theory, where moment generating functions of a random variable \(X\), defined as:

(with \(\mathbf{E}\) denoting expectation) encodes the moments of the distribution of \(X\), with:

Another application is in statistical mechanics, where the derivatives of the logarithm of a system’s partition function encodes the mean energy (and other related quantities) of the system. Surprisingly, this tool comes in useful for combinatorics problems, such as solving for the Fibonacci numbers! To this end, we define a power series \(F(x)\) such that the coefficients are the Fibonacci numbers:

We can then apply the recursion relation Eq. \eqref{eq:fibonacci} termwise to obtain the expression:

where we let \(f_{-2} = f_{-1} = 0\), and the extra \(x\) on the right hand side is present to enforce \(f_1 = 1\). Factoring some powers of \(x\), we find:

and re-indexing the series on the left hand side and applying the definition of the Fibonacci generating function, we find:

We may then isolate \(F(x)\) to obtain:

\(x^2 + x - 1\) has the two roots \(x = \frac{-1 \pm \sqrt{5}}{2}\), or in terms of the golden ratio, \(x = \varphi - 1\) and \(x = -\varphi\). We may then write:

By partial fraction decomposition, we have:

Using the identity \(\varphi - 1 = \frac{1}{\varphi}\), we may rewrite this as:

Now using the geometric series formula for both terms:

Since the coefficients of \(F(x)\) are the Fibonacci numbers by definition, we conclude that:

which we can see agrees with our previous result from the linear algebra approach.

Acknowledgements

Thank you to Yaniv Plan/Richard Anstee for presenting the clever diagonalization approach in MATH 223 (Honours Linear Algebra), and to 3Blue1Brown for his fantastic video on using generating functions to solve problems in combinatorics.