Fibonacci sequence
In mathematics, the Fibonacci sequence is a sequence in which each element is the sum of the two elements that precede it. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted. Many writers begin the sequence with 0 and 1, although some authors start it from 1 and 1 and some from 1 and 2. Starting from 0 and 1, the sequence begins
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 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 relationand
for.
Under some older definitions, the value is omitted, so that the sequence starts with and the recurrence is valid for.
The first 20 Fibonacci numbers are:
The Fibonacci sequence can be extended to negative integer indices by following the same recurrence relation in the negative direction :,, and for. Nearly all properties of Fibonacci numbers do not depend upon whether the indices are positive or negative. The values for positive and negative indices obey the relation:
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 syllables of 2 units duration, juxtaposed with short 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. Singh cites Pingala's cryptic formula misrau cha and scholars who interpret it in context as saying that the number of patterns for beats is obtained by adding one to the cases and one to the cases. Bharata Muni also expresses knowledge of the sequence in the Natya Shastra.
However, the clearest exposition of the sequence arises in the work of Virahanka, whose own work is lost, but is available in a quotation by Gopala :
Variations of two earlier meters ... For example, for four, variations of meters of two three being mixed, five happens. ... In this way, the process should be followed in all mātrā-vṛttas .
Hemachandra 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 Liber Abaci by Fibonacci, where it is used to calculate the growth of rabbit populations. Fibonacci considers the growth of an idealized 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 rabbit math problem: 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.
The name "Fibonacci sequence" was first used by the 19th-century number theorist Édouard Lucas.
Relation to the golden ratio
Closed-form expression
Like every sequence defined by a homogeneous 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:where is the golden ratio and is its conjugate,
The numbers and are the two solutions of the quadratic equation, that is,, and thus they satisfy the identities and.
Since, Binet's formula can also be written as
To see the relation between the sequence and these constants, note that and are also roots of so the powers of and satisfy the Fibonacci recurrence. In other words,
It follows that for any values and, the sequence defined by
satisfies the same recurrence. 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:
which has solution
producing the required formula.
Taking the starting values and to be arbitrary constants and solving the system of equations gives the general solution
In particular, choosing makes the -th element of the sequence closely approximate the -th power of for large enough values of. This arises when and, which produces the sequence of Lucas numbers.
Computation by rounding
Sincefor all, the number is the closest integer to. Therefore, it can be found by rounding, using the nearest integer function:
In fact, the rounding error quickly becomes very small as grows, being less than 0.1 for, and less than 0.01 for. This formula is easily inverted to find an index of a Fibonacci number :
Instead using the floor function gives the largest index of a Fibonacci number that is not greater than :
where,, and.
Magnitude
Since Fn is asymptotic to, the number of digits in is asymptotic to. As a consequence, for every integer there are either 4 or 5 Fibonacci numbers with decimal digits.More generally, in the base representation, the number of digits in is asymptotic to
Limit of consecutive quotients
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 these ratios approach the golden ratio :This convergence holds regardless of the starting values and, unless. This can be verified using Binet's formula. For example, the initial values 3 and 2 generate the sequence 3, 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, 343, 555,... . The ratio of consecutive elements in this sequence shows the same convergence towards the golden ratio.
In general,, because the ratios between consecutive Fibonacci numbers approaches.
Decomposition of powers
Since the golden ratio satisfies the equationthis expression can be used to decompose higher powers as a linear function of lower powers, which in turn can be decomposed all the way down to a linear combination of and 1. The resulting recurrence relationships yield Fibonacci numbers as the linear coefficients:
This equation can be proved by induction on :
For, it is also the case that and it is also the case that
These expressions are also true for if the Fibonacci sequence Fn is extended to negative integers using the Fibonacci rule
Identification
Binet's formula provides a proof that a positive integer is a Fibonacci number if and only if at least one of or is a perfect square. This is because Binet's formula, which can be written as, can be multiplied by and solved as a quadratic equation in via the quadratic formula:Comparing this to, it follows that
In particular, the left-hand side is a perfect square.
Matrix form
A 2-dimensional system of linear difference equations that describes the Fibonacci sequence isalternatively denoted
which yields. The eigenvalues of the matrix are and corresponding to the respective eigenvectors
As the initial value is
it follows that the th element is
From this, the th element in the Fibonacci series may be read off directly as a closed-form expression:
Equivalently, the same computation may be performed by diagonalization of through use of its eigendecomposition:
where
The closed-form expression for the th element in the Fibonacci series is therefore given by
which again yields
The matrix has a determinant of −1, and thus it is a unimodular matrix.
This property can be understood in terms of the continued fraction representation for the golden ratio :
The convergents of the continued fraction for are ratios of successive Fibonacci numbers: is the -th convergent, and the -st convergent can be found from the recurrence relation. The matrix formed from successive convergents of any continued fraction has a determinant of +1 or −1. The matrix representation gives the following closed-form expression for the Fibonacci numbers:
For a given, this matrix can be computed in arithmetic operations, using the exponentiation by squaring method.
Taking the determinant of both sides of this equation yields Cassini's identity,
Moreover, since for any square matrix, the following identities can be derived,
In particular, with,
These last two identities provide a way to compute Fibonacci numbers recursively in arithmetic operations. This matches the time for computing the -th Fibonacci number from the closed-form matrix formula, but with fewer redundant steps if one avoids recomputing an already computed Fibonacci number.