This site is supported by donations to The OEIS Foundation.

# Fibonacci numbers

The Fibonacci sequence is named after Leonardo of Pisa, who was known as Fibonacci (a contraction of filius Bonacci, son of Bonaccio). Fibonacci's 1202 book Liber Abaci introduced the sequence to Western European mathematics, although the sequence had been previously described in Indian mathematics.

## Recurrence equation

The Fibonacci numbers are defined by the following homogeneous linear recurrence of order 2 and signature (1, 1) (Cf. Category:Recurrence, linear, order 02, (1,1))

$F_0 \equiv 0,\,$
$F_1 \equiv 1,\,$
$F_n = F_{n-1} + F_{n-2},\,$

which gives the sequence (Cf. A000045)

{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, ...}

## Binet's closed-form formula

$F_n = \frac{\phi^n - \varphi^n}{\phi - \varphi} = \frac{\phi^n - \varphi^n}{\sqrt{5}}\,$

where

$\phi = \frac{1+\sqrt{5}}{2},\ \varphi = \frac{1-\sqrt{5}}{2}\,$,

$\scriptstyle \phi\,$ being the Golden ratio, are the roots of

$x^2-x-1 = 0.\,$

Since

$x^2 = x^1 + x^0\,$

implies

$x^{n+2} = x^{n+1} + x^{n+0}\,$

notice how it compares with the recurrence for the Fibonacci numbers

$F_{n+2} = F_{n+1} + F_{n+0}\,$

## Limit of consecutive quotients

Johannes Kepler observed that the ratio of consecutive Fibonacci numbers converges. He wrote that "as 5 is to 8 so is 8 to 13, practically, and as 8 is to 13, so is 13 to 21 almost”, and concluded that the limit approaches the golden ratio

$\lim_{n\to\infty}\frac{F_{n+1}}{F_{n}} = \phi\,$