Fibonacci sequence

The Fibonacci sequence is described by the recurrence relation

with initial conditions and .

This sequence can be motivated by the following scenario:

A newly born breeding pair of rabbits are put in a field; each breeding pair mates at the age of one month, and at the end of their second month they always produce another pair of rabbits; and rabbits never die, but continue breeding forever.

Close-Form Solution

Main: Binet’s Formula

The close form solution of the Fibonacci numbers is given by the Binet’s Formula:

where is the golden ratio.

Info

Since , Fibonacci numbers converges to for large and the ratio of consecutive Fibonacci numbers converges to the golden ratio .

In Programming

Recursive Approach

A recursive implementation of the Fibonacci numbers directly translates from the recurrence relation is highly inefficient.

def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

While this approach is highly ineffective (exponential time), it is still often used as a benchmark for programming languages performing computationally intensive tasks or as a demonstration of parallel algorithms.

Iterative Approach

While we can make the above implementation more efficient with memoization, a iterative approach also exists:

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a+b
    return a

Exponentiating By Squaring

By recognizing the above computation as a linear transformation, we can rewrite it to a matrix multiplication:

As matrix multiplication is associative, we can use the exponentiating by squaring method to get the result in :

def matrix_mult(A, B):
    return [
      [A[0][0] * B[0][0] + A[0][1] * B[1][0],
       A[0][0] * B[0][1] + A[0][1] * B[1][1]],
      [A[1][0] * B[0][0] + A[1][1] * B[1][0],
       A[1][0] * B[0][1] + A[1][1] * B[1][1]]]
 
def matrix_pow(A, n):
    result = [[1, 0], [0, 1]]
    while n > 0:
        if n % 2 == 1:
            result = matrix_mult(result, A)
        A = matrix_mult(A, A)
        n //= 2
    return result
 
def fib(n):
    A = [[1, 1], [1, 0]]
    result = matrix_pow(A, n)
    return result[1][0]

See power of monoid for a generic solution using monoid.

Binet’s Formula

We can also use the Binet’s Formula to calculate the Fibonacci sequence. Do note that this method subjects to the floating-point precision limits.

def fib(n):
    phi = (1 + sqrt(5)) / 2
    psi = (1 - sqrt(5)) / 2
    return round((phi**n - psi**n) / sqrt(5))

See Also

• golden ratio