Fibonacci Sequence

The recurrence

Fibonacci sequence is defined by:

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

So the sequence starts — 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, ...

Each term is the sum of the two before. Mathematically, this is the simplest non-trivial linear recurrence, and it has surprisingly rich properties.

Binet's closed-form formula

The closed form for F(n):

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

where:
  φ = (1 + √5) / 2 ≈ 1.6180339...   (golden ratio)
  ψ = (1 − √5) / 2 ≈ −0.6180339...   (the other root)

Since |ψ| < 1, ψⁿ shrinks toward zero. So for any reasonable n:

F(n) ≈ φⁿ / √5    (round to nearest integer)

F(10) = 55. φ¹⁰ / √5 ≈ 55.003. Round to 55. ✓

F(20) = 6765. φ²⁰ / √5 ≈ 6765.000. Exact integer when rounded.

Why naive recursion is exponential

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

Time complexity is O(φⁿ) ≈ O(1.618ⁿ). For n = 50, that's ≈ 12.6 billion calls — minutes to hours. The recursion tree has roughly Fibonacci-many nodes, hence the exponential.

Memoization fixes this:

function fibMemo(n, memo = {}) {
  if (n < 2) return n;
  if (memo[n] !== undefined) return memo[n];
  return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
}

Each F(k) computed once. O(n) time, O(n) space. F(50) computes in milliseconds.

Bottom-up iteration uses constant space:

function fibIter(n) {
  let prev = 0, curr = 1;
  for (let i = 0; i < n; i++) [prev, curr] = [curr, prev + curr];
  return prev;
}

Matrix exponentiation — O(log n)

The Fibonacci recurrence can be written as a matrix:

[F(n+1)]   [1  1] [F(n)  ]
[F(n)  ] = [1  0] [F(n-1)]

Iterating gives:

[F(n+1)]   [1  1]ⁿ [1]
[F(n)  ] = [1  0]  [0]

Matrix exponentiation by squaring computes the n-th power in O(log n) matrix multiplications. So Fibonacci can be computed in O(log n) — even faster than linear iteration. Used for huge n in competitive programming.

JavaScript implementations

// Naive recursion (slow)
const fibNaive = n => n < 2 ? n : fibNaive(n-1) + fibNaive(n-2);

// Memoized recursion (linear)
const memo = new Map();
function fibMemo(n) {
  if (n < 2) return n;
  if (memo.has(n)) return memo.get(n);
  const result = fibMemo(n - 1) + fibMemo(n - 2);
  memo.set(n, result);
  return result;
}

// Iterative (linear, constant space)
function fibIter(n) {
  if (n < 2) return n;
  let prev = 0, curr = 1;
  for (let i = 1; i < n; i++) [prev, curr] = [curr, prev + curr];
  return curr;
}

// Matrix exponentiation (logarithmic)
function fibMatrix(n) {
  if (n === 0) return 0;
  function multiply(A, B) {
    return [
      [A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]],
      [A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]]
    ];
  }
  function power(M, p) {
    if (p === 1) return M;
    if (p % 2 === 0) {
      const half = power(M, p / 2);
      return multiply(half, half);
    }
    return multiply(M, power(M, p - 1));
  }
  const result = power([[1, 1], [1, 0]], n);
  return result[0][1];
}

// Binet's formula (limited precision for large n)
const phi = (1 + Math.sqrt(5)) / 2;
const fibBinet = n => Math.round(Math.pow(phi, n) / Math.sqrt(5));

// All agree for moderate n
console.log(fibIter(20), fibMatrix(20), fibBinet(20));  // all 6765

Fascinating properties

• Sum identity — F(1) + F(2) + ... + F(n) = F(n+2) − 1.
• Square sum — F(1)² + F(2)² + ... + F(n)² = F(n) · F(n+1).
• Even-odd alternation — every third Fibonacci is even.
• Multiplicative property — F(m+n) = F(m+1)·F(n) + F(m)·F(n−1).
• GCD property — gcd(F(m), F(n)) = F(gcd(m, n)).
• Pisano period — Fibonacci mod m is eventually periodic.
• Cassini's identity — F(n−1)·F(n+1) − F(n)² = (−1)ⁿ.

Fibonacci in nature

• Sunflower seeds. Spirals appear in counts that are typically adjacent Fibonacci numbers — 34/55, 55/89, 89/144. The optimal packing arrangement of seeds.
• Pinecones. Spiral counts of scales are Fibonacci. Most pinecones — 8 spirals one direction, 13 the other.
• Pineapple bumps. Three different Fibonacci spiral counts — typically 8, 13, 21.
• Flower petals. Lily — 3, buttercup — 5, delphinium — 8, marigold — 13, aster — 21, daisy — 34, 55, or 89. All Fibonacci.
• Plant growth. New leaves placed at the golden angle (~137.5°) avoid blocking sunlight to lower leaves. The golden angle is 360°·(1 − 1/φ).
• DNA structures and animal bodies. Some patterns — but watch out for confirmation bias. Not every "spiral in nature" is Fibonacci; many genuinely are.

Where Fibonacci shows up in computing

• Algorithm analysis. Worst case for Euclidean algorithm — adjacent Fibonacci pairs take O(log_φ n) steps.
• Fibonacci heaps. Theoretical priority queue with O(1) amortized decrease-key. Used (rarely) for theoretical Dijkstra speedups.
• Recursion teaching. The textbook example of recursion vs iteration vs memoization.
• Random search algorithms. Fibonacci search — variant of binary search using Fibonacci-spaced split points.
• Combinatorics. F(n) counts the number of ways to climb n stairs taking 1 or 2 at a time, the number of binary strings of length n with no consecutive 1s, etc.

Common mistakes

• Off-by-one in indexing. Some texts start with F(1) = F(2) = 1 (skipping F(0) = 0). Others start F(0) = 0, F(1) = 1. Always check the convention; off-by-one can throw all subsequent values.
• Naive recursion for large n. O(2ⁿ) is the textbook anti-example. Always memoize or iterate.
• Floating-point Binet for large n. Binet's formula is exact in algebra but loses precision in floating-point. For n > ~70, use integer arithmetic (matrix exponentiation or iteration).
• Integer overflow. F(50) is about 12 billion — beyond 32-bit signed integer range. F(80) overflows 64-bit signed integers. Use BigInt for large indices.
• Generalizing without checking. "Linear recurrences are all this fast" — most are O(n). Some require matrix exponentiation. Read the recurrence; don't assume.
• Believing every spiral is Fibonacci. Confirmation bias — people see patterns where there aren't any. Many "Fibonacci in nature" claims are real; some are exaggerated. Verify with measurements.