This site is supported by donations to The OEIS Foundation.

Fibonacci numbers

From OeisWiki

Jump to: navigation, search

This article needs more work.

Please contribute in expanding it!


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.

Contents

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\,

See also

Personal tools