Fibonacci Sequence Generator

About the Fibonacci Sequence

The person who described this sequence was the mathematician Leonardo of Pisa, known as Fibonacci, back in the 13th century. You add the two preceding terms to reach the next one: 0, 1, 1, 2, 3, 5, 8, 13… As it goes on, the ratio between two consecutive terms closes in on the golden ratio φ ≈ 1.618, a number that turns up in natural patterns, from flowers and shells to galaxies.

The Fibonacci sequence and the golden ratio

The Fibonacci sequence is defined recursively as F₀ = 0, F₁ = 1 and Fₙ = Fₙ₋₁ + Fₙ₋₂ for n ≥ 2. The first terms are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144… Binet's formula gives a closed form: Fₙ = (φⁿ − ψⁿ) / √5, where φ = (1+√5)/2 ≈ 1.618 is the golden ratio and ψ = (1−√5)/2. The ratio Fₙ₊₁/Fₙ converges to φ. The sequence first appeared in Europe in the Liber Abaci (1202), where Leonardo of Pisa — Fibonacci — used it to model rabbit reproduction. Algorithmic notes: a naive recursive implementation runs in O(2ⁿ) time (exponential, with many recomputed subproblems), iterative or memoized versions are O(n), and Binet's formula is O(1) but accumulates floating-point error for large n; matrix exponentiation gives O(log n).

Applications: nature, art and finance

Fibonacci numbers appear in nature (phyllotaxis — petal counts, spirals in sunflowers, pinecones and pineapples), art and architecture (Le Corbusier's Modulor), music (composers including Béla Bartók structured passages around Fibonacci ratios) and in technical analysis of financial markets (Fibonacci retracements: 23.6%, 38.2%, 61.8%).

FAQ

Does the sequence start at 0 or 1? The most common modern definition starts at F₀ = 0, F₁ = 1. Some older texts use F₁ = F₂ = 1; the values shift index by 1.

What is the golden ratio? The number φ ≈ 1.6180339… satisfies φ² = φ + 1. It is the limit of Fₙ₊₁/Fₙ.

Why is naive recursion slow? Each call branches into two more, recomputing the same values exponentially many times. Memoization or iteration reduces it to linear time.

Are Fibonacci numbers really everywhere in nature? They appear often in phyllotaxis and spiral packings, but the "Fibonacci-in-everything" claim is overstated — many cases are coincidence or selection bias.