The Fibonacci sequence

The Fibonacci sequence is one of the most famous mathematical sequences, defined recursively:

F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) for n ≥ 2

First 20 terms:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181

Published by Leonardo Pisano (Fibonacci) in Liber Abaci (1202), which also introduced Arabic numerals to Europe (0-9 replacing Roman numerals).

The golden ratio φ

The ratio between consecutive Fibonacci terms converges to the golden ratio:

φ (phi) = (1 + √5) / 2 ≈ 1.6180339887...

Notable properties:

• φ² = φ + 1 (the only positive solution of x² = x + 1)
• 1/φ = φ − 1 ≈ 0.618
• φ is irrational, like π and e
• "The most irrational of numbers": best rational approximation uses Fibonacci numbers themselves

Binet's formula

Closed form for the nth term without recursion (Jacques Binet, 1843, but known to de Moivre 1718):

F(n) = (φⁿ − ψⁿ) / √5

where ψ = (1 − √5)/2 ≈ −0.618 is the "conjugate" of φ.

For large n, ψⁿ → 0, so:

F(n) ≈ φⁿ / √5

Surprisingly accurate even from n = 5.

Notable identities

• Cassini: F(n-1)·F(n+1) − F(n)² = (−1)ⁿ
• Catalan: F(n)² − F(n-r)·F(n+r) = (−1)^n-r·F(r)²
• Sum: F(0) + F(1) + ... + F(n) = F(n+2) − 1
• Even sum: F(0) + F(2) + ... + F(2n) = F(2n+1) − 1
• D'Ocagne: F(m)·F(n+1) + F(m-1)·F(n) = F(m+n)
• Divisibility: F(n) divides F(n·k) for any integer k
• Coprimes: gcd(F(m), F(n)) = F(gcd(m, n))

Lucas numbers

Closely related sequence:

L(0) = 2, L(1) = 1, L(n) = L(n-1) + L(n-2)

First terms: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843

Relations with Fibonacci:

• L(n) = F(n-1) + F(n+1)
• F(n)·L(n) = F(2n)
• L(n)² = 5·F(n)² + 4·(−1)ⁿ

Fibonacci in nature

Plant spirals (phyllotaxis)

Leaves on a stem, petals, sunflower spirals follow angles based on golden angle 137.5° = 360°·(2-φ). Maximizes light and water exposure.

Sunflower seeds

Arranged in two spiral series: 34 one way and 55 the other (both Fibonacci), or 55 and 89 depending on size.

Pinecone

Typically 8 and 13 spirals (F(6) and F(7)).

Nautilus shell

Approximate golden logarithmic spiral (not exact).

Pineapple

8, 13, and 21 spirals.

Honeybee ancestry

A drone has only mother (no father). Ancestor tree: 1 mother, 2 grandparents, 3 great-grandparents, 5, 8, 13... Fibonacci!

Fibonacci in art and architecture

• Parthenon Athens (~447-432 BCE): golden ratios in proportions
• Great Pyramid of Giza (~2560 BCE): some ratios approximate φ (historical debate)
• Leonardo da Vinci: Vitruvian Man, Mona Lisa, Last Supper
• Le Corbusier: Modulor system (1948) based on φ + human proportions
• Salvador Dalí: Sacrament of the Last Supper (1955) with Kepler-Poinsot dodecahedron

Fibonacci in finance

Technical market analysts use Fibonacci retracements: levels 23.6%, 38.2%, 50%, 61.8%, 78.6% based on Fibonacci ratios.

Mathematical basis: 0.618 and 0.382 are 1/φ and 1/φ² respectively.

Note: correlation between Fibonacci and market movements is scientifically debated; many economists view levels as "self-fulfilling prophecy" rather than natural law.

Algorithmic complexity

1. Naive recursion

function fib(n) { return n < 2 ? n : fib(n-1) + fib(n-2); }

Complexity: O(φⁿ) — exponential, unusable for n > 40.

2. Iterative

function fib(n) {
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) { [a, b] = [b, a+b]; }
  return b;
}

Complexity: O(n) — straightforward up to thousands.

3. Matrix

Using (1 1; 1 0)ⁿ with fast exponentiation:

Complexity: O(log n) — for huge n.

4. Binet

Closed form O(1) but with errors for large n (floating point precision).

Fibonacci in computer science

• Fibonacci search: sorted array search algorithm using Fibonacci instead of half
• Fibonacci heap: data structure for Dijkstra O((V+E)log V), used in network routing
• Fibonacci hashing: hash function based on φ, extremely uniform distribution
• PRNG: Lagged Fibonacci generator
• Data compression: some techniques use Fibonacci sequences

Pascal's Triangle and Fibonacci

Summing diagonals of Pascal's Triangle gives Fibonacci numbers. Surprising connection between combinatorics and Fibonacci recursion.

Generalizations

Different seeds

Starting F(

• = a, F(
• = b: F(n) = a·F_Fib(n-
• + b·F_Fib(n-1)

Tribonacci

T(n) = T(n-1) + T(n-2) + T(n-3). Limit ratio ≈ 1.839.

k-Nacci

Generalization to k previous terms.

φ vs π and e

Three most famous mathematical constants:

All three are irrational and transcendental.

History

• ~200 BCE Pingala (India): first historical appearance in Vedic rhythm
• ~1202 Leonardo of Pisa (Fibonacci): Liber Abaci, rabbit problem
• ~1611 Johannes Kepler: notes ratio convergence to φ, botanical connection
• ~1718 Abraham de Moivre: first closed form (unpublished)
• ~1843 Jacques Binet: reproduces closed form, gets popular name
• ~1963: Fibonacci Quarterly journal founded

The rabbit problem

From Liber Abaci 1202: "A man puts a pair of rabbits in an enclosed place. How many pairs after a year, assuming each month a pair produces another that becomes productive the second month?"

Month 1: 1 pair, Month 2: 1 (not yet fertile), Month 3: 2, ..., Month 12: 144 pairs.

Biologically unrealistic but pedagogically brilliant.

Excel / Sheets / Python functions

Excel / Google Sheets

No native function. Use recursion or Binet:

=ROUND((PHI^A1 − (1−PHI)^A1) / SQRT(5), 0)
where PHI = (1+SQRT(5))/2

Python

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

[fib(i) for i in range(10)]  # [0,1,1,2,3,5,8,13,21,34]

from functools import cache
@cache
def fib_rec(n):
    return n if n < 2 else fib_rec(n-1) + fib_rec(n-2)

Common mistakes

• Overflow: F(79) ≈ 14 × 10¹⁵ exceeds int32. Use int64 or BigInt
• Naive recursion: O(φⁿ) terrible — memoize or iterate
• Index confusion: some definitions use F(1)=F(2)=1 (without F(0)=0)
• Binet precision: for n > 70, floating point errors accumulate

FAQ

Why does Fibonacci appear in nature?

Golden ratio minimizes overlap and maximizes efficiency. 137.5° between leaves allows maximum light exposure without shadowing.

Is golden ratio really everywhere?

Some appearances are documented and verifiable (phyllotaxis). Many attributions in art/architecture are exaggerated or fabricated after the fact. Mysticism around φ is real but inflated.

How to calculate F(1000)?

Don't use recursion. Iterate O(n) with BigInt. Python handles large numbers natively: F(1000) has 209 digits.

Other beautiful ratios?

Plastic number ψ ≈ 1.3247 (van der Laan constant, architecture). Silver ratio 1+√2 ≈ 2.414. Supergolden ratio ψ³ = ψ² + 1.

Does Fibonacci have modern applications?

Yes: cryptography (Fibonacci hashing), number theory, computer graphics, ML (Fibonacci heap).

Updated July 2026