Editing Fibonacci sequence (section)

{{Short description|Numbers obtained by adding the two previous ones}}
{{For|the chamber ensemble|Fibonacci Sequence (ensemble)}}

In mathematics, the '''Fibonacci sequence''' is a [[Integer sequence|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 {{nowrap|{{math|''F<sub>n</sub>''}}{{space|hair}}}}. Many writers begin the sequence with 0 and 1, although some authors start it from 1 and 1<ref>Richard A. Brualdi, ''Introductory Combinatorics'', Fifth edition, Pearson, 2005</ref><ref>Peter Cameron, ''Combinatorics: Topics, Techniques, Algorithms'', Cambridge University Press, 1994</ref> and some (as did Fibonacci) from 1 and 2. Starting from 0 and 1, the sequence begins
: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... {{OEIS|A000045}}

[[File:Fibonacci Squares.svg|thumb|A tiling with [[square]]s whose side lengths are successive Fibonacci numbers: 1, 1, 2, 3, 5, 8, 13 and 21]]
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.<ref name="GlobalScience" /><ref name="HistoriaMathematica" /><ref name="Donald Knuth 2006 50" /> 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 {{lang|la|[[Liber Abaci]]}}.{{Sfn|Sigler|2002|pp=404–05}}

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 [[graph (discrete mathematics)|graphs]] called [[Fibonacci cube]]s used for interconnecting parallel and distributed systems. They also appear [[Patterns in nature#Spirals|in biological settings]], such as branching in trees, [[phyllotaxis|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|Binet's formula]] expresses the {{mvar|n}}-th Fibonacci number in terms of {{mvar|n}} and the golden ratio, and implies that the ratio of two consecutive Fibonacci numbers tends to the golden ratio as {{mvar|n}} increases. Fibonacci numbers are also closely related to [[Lucas number]]s, which obey the same [[recurrence relation]] and with the Fibonacci numbers form a complementary pair of [[Lucas sequence]]s.