Fibonacci sequence explained

In mathematics, the Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted . The sequence commonly starts from 0 and 1, although some authors start the sequence from 1 and 1 or sometimes (as did Fibonacci) from 1 and 2. Starting from 0 and 1, the sequence begins^[1]

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ....

The Fibonacci numbers were first described in Indian mathematics as early as 200 BC in work by Pingala on enumerating possible patterns of Sanskrit poetry formed from syllables of two lengths. They are named after the Italian mathematician Leonardo of Pisa, also known as Fibonacci, who introduced the sequence to Western European mathematics in his 1202 book Latin: [[Liber Abaci]].

Fibonacci numbers appear unexpectedly often in mathematics, so much so that there is an entire journal dedicated to their study, the Fibonacci Quarterly. Applications of Fibonacci numbers include computer algorithms such as the Fibonacci search technique and the Fibonacci heap data structure, and graphs called Fibonacci cubes used for interconnecting parallel and distributed systems. They also appear in biological settings, such as branching in trees, the arrangement of leaves on a stem, the fruit sprouts of a pineapple, the flowering of an artichoke, and the arrangement of a pine cone's bracts, though they do not occur in all species.

Fibonacci numbers are also strongly related to the golden ratio: Binet's formula expresses the -th Fibonacci number in terms of and the golden ratio, and implies that the ratio of two consecutive Fibonacci numbers tends to the golden ratio as increases. Fibonacci numbers are also closely related to Lucas numbers, which obey the same recurrence relation and with the Fibonacci numbers form a complementary pair of Lucas sequences.

Definition

The Fibonacci numbers may be defined by the recurrence relation $F_0=0,\quad F_1= 1,$ and $F_n=F_ + F_$ for .

Under some older definitions, the value

F₀=0

is omitted, so that the sequence starts with

F_1=F_2=1,

and the recurrence

F_n=F_n-1+F_n-2

is valid for .

The first 20 Fibonacci numbers are:^[1]

History

India

The Fibonacci sequence appears in Indian mathematics, in connection with Sanskrit prosody. In the Sanskrit poetic tradition, there was interest in enumerating all patterns of long (L) syllables of 2 units duration, juxtaposed with short (S) syllables of 1 unit duration. Counting the different patterns of successive L and S with a given total duration results in the Fibonacci numbers: the number of patterns of duration units is .

Knowledge of the Fibonacci sequence was expressed as early as Pingala ( 450 BC–200 BC). Singh cites Pingala's cryptic formula misrau cha ("the two are mixed") and scholars who interpret it in context as saying that the number of patterns for beats is obtained by adding one [S] to the cases and one [L] to the cases. Bharata Muni also expresses knowledge of the sequence in the Natya Shastra (c. 100 BC–c. 350 AD).However, the clearest exposition of the sequence arises in the work of Virahanka (c. 700 AD), whose own work is lost, but is available in a quotation by Gopala (c. 1135):

Variations of two earlier meters [is the variation] ... For example, for [a meter of length] four, variations of meters of two [and] three being mixed, five happens. [works out examples 8, 13, 21] ... In this way, the process should be followed in all mātrā-vṛttas [prosodic combinations].

Hemachandra (c. 1150) is credited with knowledge of the sequence as well, writing that "the sum of the last and the one before the last is the number ... of the next mātrā-vṛtta."

Europe

The Fibonacci sequence first appears in the book Latin: [[Liber Abaci]] (The Book of Calculation, 1202) by Fibonacci where it is used to calculate the growth of rabbit populations. Fibonacci considers the growth of an idealized (biologically unrealistic) rabbit population, assuming that: 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. Fibonacci posed the puzzle: how many pairs will there be in one year?

At the end of the first month, they mate, but there is still only 1 pair.
At the end of the second month they produce a new pair, so there are 2 pairs in the field.
At the end of the third month, the original pair produce a second pair, but the second pair only mate to gestate for a month, so there are 3 pairs in all.
At the end of the fourth month, the original pair has produced yet another new pair, and the pair born two months ago also produces their first pair, making 5 pairs.

At the end of the -th month, the number of pairs of rabbits is equal to the number of mature pairs (that is, the number of pairs in month) plus the number of pairs alive last month (month). The number in the -th month is the -th Fibonacci number.

The name "Fibonacci sequence" was first used by the 19th-century number theorist Édouard Lucas.

Relation to the golden ratio

See main article: Golden ratio.

Closed-form expression

Like every sequence defined by a linear recurrence with constant coefficients, the Fibonacci numbers have a closed-form expression. It has become known as Binet's formula, named after French mathematician Jacques Philippe Marie Binet, though it was already known by Abraham de Moivre and Daniel Bernoulli:

$F_n = \frac = \frac,$

where

$\varphi = \frac \approx 1.61803\,39887\ldots$

is the golden ratio, and is its conjugate:

$\psi = \frac = 1 - \varphi = - \approx -0.61803\,39887\ldots.$

Since

\psi=-\varphi^-1

, this formula can also be written as

$F_n = \frac = \frac.$

To see the relation between the sequence and these constants, note that and are both solutions of the equation $x^2 = x + 1$ and thus

xⁿ=x^n-1+x^n-2,

so the powers of and satisfy the Fibonacci recursion. In other words,

$\begin\varphi^n &= \varphi^ + \varphi^, \\[3mu]\psi^n &= \psi^ + \psi^.\end$

It follows that for any values and, the sequence defined by

$U_n=a \varphi^n + b \psi^n$

satisfies the same recurrence,

$\beginU_n &= a\varphi^n + b\psi^n \\[3mu]&= a(\varphi^ + \varphi^) + b(\psi^ + \psi^) \\[3mu]&= a\varphi^ + b\psi^ + a\varphi^ + b\psi^ \\[3mu]&= U_ + U_.\end$

If and are chosen so that and then the resulting sequence must be the Fibonacci sequence. This is the same as requiring and satisfy the system of equations:

$\left\$

Notes and References

A000045. Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1. cs2.