The Fibonacci 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.

This problem can be described by the recurrence relation

with initial conditions and

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

A recursive implementation of the Fibonacci numbers directly translated from the recurrence relation is highly inefficient, but it is still often used as a benchmark for programming languages performing computationally intensive tasks or as a demonstration of parallel algorithms.

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

While we can make this implementation 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

For computing very large Fibonacci numbers, we can also use the close-form solution.

See Also