Fibonacci number

Definition and basic properties

The sequence is defined by the recurrence relation F_n = F_{n-1} + F_{n-2} for integer n greater than the chosen starting index. With the widely used starting values F_0 = 0 and F_1 = 1, the recurrence yields the standard sequence. Some sources index the sequence from 1, taking F_1 = 1 and F_2 = 1; both conventions are common and differ only by an index shift. The ratio of consecutive Fibonacci numbers F_{n+1}/F_n converges to the golden ratio (approximately 1.618), a constant that appears in geometry and aesthetics.

History and origin

The sequence is named after Leonardo of Pisa (Fibonacci), who described it in his 1202 work Liber Abaci, which introduced Hindu–Arabic numerals and certain computational problems to Western Europe. However, versions of the sequence and related combinatorial identities were known earlier in Indian mathematics. Over centuries the sequence has been studied for its arithmetic properties, combinatorial interpretations, and relationships to continued fractions and algebraic identities.

Examples, interpretations and occurrences

Fibonacci numbers appear in a variety of counting problems and natural arrangements. Classic textbook interpretations include the model of rabbit population growth and tilings of a strip with squares and dominoes, where the number of ways to tile a length-n strip equals a Fibonacci number. In nature, leaf arrangements, branching patterns, and spirals of seeds and shells often show counts or ratios related to Fibonacci numbers or the golden ratio, though patterns in biology are shaped by growth constraints as well as mathematics.

• Combinatorial: counts of certain binary strings, tilings, and lattice paths.
• Algebraic: closed-form expression using the golden ratio (Binet's formula) gives an explicit value for F_n without recursion.
• Number-theoretic: divisibility patterns and relations with Lucas numbers and binomial sums.

Applications, computation and notable facts

Fibonacci numbers are used in algorithm analysis, pseudorandom structures, and recreational mathematics. Efficient algorithms compute large Fibonacci numbers using matrix exponentiation or the fast doubling method. The sequence relates to continued fractions, to the minimal polynomial of the golden ratio, and to other integer sequences such as Lucas numbers. Extensions include generalized Fibonacci sequences where different starting values or order (sums of more than two preceding terms) are used, and negative-index Fibonacci numbers (the negafibonacci sequence) that extend the recurrence to all integers.

Further reading and distinctions

When consulting sources about the sequence, note the indexing choice (starting at F_0 or F_1) and whether closed-form formulas, limiting ratios, or combinatorial interpretations are the focus. For a general introduction and historical context see works on number sequences and medieval mathematics; for algorithmic aspects, search topics such as fast doubling and matrix exponentiation. The sequence is a basic example linking simple recurrence definitions to deep and varied mathematical phenomena.

For related entries and external resources visit general pages on mathematics and historical treatments of numeration and calculation; for origins predating the European rediscovery see studies of mathematical traditions in India.