Fibonacci sequence

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.

[3][4][5] 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.

[12] Bharata Muni also expresses knowledge of the sequence in the Natya Shastra (c. 100 BC–c. 350 AD).

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

[21] Like every sequence defined by a homogeneous linear recurrence with constant coefficients, the Fibonacci numbers have a closed-form expression.

Instead using the floor function gives the largest index of a Fibonacci number that is not greater than F:

Johannes Kepler observed that the ratio of consecutive Fibonacci numbers converges.

The resulting recurrence relationships yield Fibonacci numbers as the linear coefficients:

Binet's formula provides a proof that a positive integer x is a Fibonacci number if and only if at least one of

From this, the nth element in the Fibonacci series may be read off directly as a closed-form expression:

This property can be understood in terms of the continued fraction representation for the golden ratio φ:

For a given n, this matrix can be computed in O(log n) arithmetic operations, using the exponentiation by squaring method.

These last two identities provide a way to compute Fibonacci numbers recursively in O(log n) arithmetic operations.

This matches the time for computing the n-th Fibonacci number from the closed-form matrix formula, but with fewer redundant steps if one avoids recomputing an already computed Fibonacci number (recursion with memoization).

[32] Most identities involving Fibonacci numbers can be proved using combinatorial arguments using the fact that

Infinite sums over reciprocal Fibonacci numbers can sometimes be evaluated in terms of theta functions.

and there is a nested sum of squared Fibonacci numbers giving the reciprocal of the golden ratio,

When m is large – say a 500-bit number – then we can calculate Fm (mod n) efficiently using the matrix form.

[51] 1, 3, 21, and 55 are the only triangular Fibonacci numbers, which was conjectured by Vern Hoggatt and proved by Luo Ming.

[65] Determining a general formula for the Pisano periods is an open problem, which includes as a subproblem a special instance of the problem of finding the multiplicative order of a modular integer or of an element in a finite field.

In particular, Binet's formula may be generalized to any sequence that is a solution of a homogeneous linear difference equation with constant coefficients.

Fibonacci sequences appear in biological settings,[78] such as branching in trees, arrangement of leaves on a stem, the fruitlets of a pineapple,[79] the flowering of artichoke, the arrangement of a pine cone,[80] and the family tree of honeybees.

[81][82] Kepler pointed out the presence of the Fibonacci sequence in nature, using it to explain the (golden ratio-related) pentagonal form of some flowers.

[84] In 1830, Karl Friedrich Schimper and Alexander Braun discovered that the parastichies (spiral phyllotaxis) of plants were frequently expressed as fractions involving Fibonacci numbers.

[85] Przemysław Prusinkiewicz advanced the idea that real instances can in part be understood as the expression of certain algebraic constraints on free groups, specifically as certain Lindenmayer grammars.

[86] A model for the pattern of florets in the head of a sunflower was proposed by Helmut Vogel [de] in 1979.

Because the rational approximations to the golden ratio are of the form F( j):F( j + 1), the nearest neighbors of floret number n are those at n ± F( j) for some index j, which depends on r, the distance from the center.

Sunflowers and similar flowers most commonly have spirals of florets in clockwise and counter-clockwise directions in the amount of adjacent Fibonacci numbers,[88] typically counted by the outermost range of radii.

It has similarly been noticed that the number of possible ancestors on the human X chromosome inheritance line at a given ancestral generation also follows the Fibonacci sequence.

The male's mother received one X chromosome from her mother (the son's maternal grandmother), and one from her father (the son's maternal grandfather), so two grandparents contributed to the male descendant's X chromosome (

A tiling with squares whose side lengths are successive Fibonacci numbers: 1, 1, 2, 3, 5, 8, 13 and 21
The Fibonacci spiral: an approximation of the golden spiral created by drawing circular arcs connecting the opposite corners of squares in the Fibonacci tiling (see preceding image)
Thirteen ( F 7 ) ways of arranging long and short syllables in a cadence of length six. Eight ( F 6 ) end with a short syllable and five ( F 5 ) end with a long syllable.
A page of Fibonacci 's Liber Abaci from the Biblioteca Nazionale di Firenze showing (in box on right) 13 entries of the Fibonacci sequence:
the indices from present to XII (months) as Latin ordinals and Roman numerals and the numbers (of rabbit pairs) as Hindu-Arabic numerals starting with 1, 2, 3, 5 and ending with 377.
Solution to Fibonacci rabbit problem : In a growing idealized population, the number of rabbit pairs form the Fibonacci sequence. At the end of the n th month, the number of pairs is equal to F n.
Successive tilings of the plane and a graph of approximations to the golden ratio calculated by dividing each Fibonacci number by the previous
The Fibonacci numbers are the sums of the diagonals (shown in red) of a left-justified Pascal's triangle .
Use of the Fibonacci sequence to count {1, 2}-restricted compositions
Fibonacci tree of height 6. Balance factors green; heights red.
The keys in the left spine are Fibonacci numbers.
Yellow chamomile head showing the arrangement in 21 (blue) and 13 (cyan) spirals. Such arrangements involving consecutive Fibonacci numbers appear in a wide variety of plants.
Illustration of Vogel's model for n = 1 ... 500
The number of possible ancestors on the X chromosome inheritance line at a given ancestral generation follows the Fibonacci sequence. (After Hutchison, L. "Growing the Family Tree: The Power of DNA in Reconstructing Family Relationships". [ 92 ] )