Definition
The Fibonacci sequence is defined by F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n ≥ 2. The first few values: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. The sequence appears in countless places: phyllotaxis, the golden ratio (consecutive ratios approach φ ≈ 1.618), Pascal's triangle diagonals, Zeckendorf representations.
Why it matters
How it works
Compute Fibonacci by direct recursion (exponential without memoization), iteration (linear), or matrix exponentiation (logarithmic). The closed form F(n) = (φⁿ - ψⁿ) / √5 where φ = (1 + √5)/2 and ψ = (1 - √5)/2 gives F(n) directly. Identities like F(n+1)F(n-1) - F(n)² = (-1)ⁿ (Cassini's identity) interconnect terms and support algebraic manipulation.