The Fibonacci Sequence: When Each Term Is the Sum of the Previous Two

The Fibonacci sequence defines itself by looking backward.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

Each number is the sum of the two before it. 1 + 1 = 2. 1 + 2 = 3. 2 + 3 = 5. And so on.

This is different from arithmetic sequences (add a constant) and geometric sequences (multiply by a constant). Fibonacci is recursive—each term depends on previous terms. The rule doesn't reference the position; it references the history.

And somehow, from this simple backward-looking rule, a pattern emerges that shows up everywhere: in pine cones, sunflower heads, spiral galaxies, and the mathematics of optimization.

The Rule

Fₙ = Fₙ₋₁ + Fₙ₋₂

with starting values F₁ = 1 and F₂ = 1.

That's it. Two seeds and a rule. Everything else follows.

The sequence grows—slowly at first, then faster. By F₂₀, we're at 6,765. By F₅₀, we're at 12,586,269,025.

The Golden Ratio Lurks Within

Here's something remarkable. Take consecutive Fibonacci numbers and divide:

• F₃/F₂ = 2/1 = 2.0
• F₄/F₃ = 3/2 = 1.5
• F₅/F₄ = 5/3 ≈ 1.667
• F₆/F₅ = 8/5 = 1.6
• F₇/F₆ = 13/8 = 1.625
• F₁₀/F₉ = 55/34 ≈ 1.618
• F₂₀/F₁₉ ≈ 1.618033988...

The ratios converge to φ ≈ 1.618033988..., the golden ratio.

This number φ satisfies φ = 1 + 1/φ, or equivalently φ² = φ + 1. It's the ratio that equals one more than its reciprocal.

The Fibonacci sequence approaches geometric growth with ratio φ. For large n, Fₙ₊₁ ≈ φ · Fₙ.

Binet's Formula: Fibonacci Without Recursion

You can calculate any Fibonacci number directly, without computing all the previous ones:

Fₙ = (φⁿ - ψⁿ) / √5

where φ = (1 + √5)/2 ≈ 1.618 and ψ = (1 - √5)/2 ≈ -0.618.

This looks impossible. The formula involves irrational numbers (√5), yet it always produces integers. The irrationals cancel out perfectly, every time.

For large n, the ψⁿ term becomes negligible (since |ψ| < 1), so:

Fₙ ≈ φⁿ / √5, rounded to the nearest integer.

The Fibonacci sequence is secretly a geometric sequence in disguise—the sum of two exponentials that happen to produce integers.

Why Fibonacci Appears in Nature

The Fibonacci numbers count something natural: the ways to tile rectangles, the branches on trees, the spirals in flowers.

Branching patterns: A tree where each branch waits one cycle before branching again produces Fibonacci branching. Many plants follow this pattern.

Spiral patterns: Sunflower seeds, pinecone scales, and pineapple eyes arrange in spirals. Count the spirals in each direction: you'll often find consecutive Fibonacci numbers (like 34 and 55).

Why? The golden angle—about 137.5°—is the angle of maximum packing efficiency. It's related to the golden ratio, which is related to Fibonacci. When nature optimizes for space, Fibonacci appears.

This isn't mystical. It's optimization. The golden ratio and Fibonacci emerge when systems grow by looking at their recent history.

Fibonacci as a Recursive Sequence

The Fibonacci sequence is the most famous example of a recurrence relation—a sequence defined by an equation involving previous terms.

General form: aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ

Fibonacci is the simplest nontrivial case: aₙ = aₙ₋₁ + aₙ₋₂.

Other famous recurrence relations:

• Lucas numbers: Same rule, different seeds (2, 1, 3, 4, 7, 11, ...)
• Tribonacci: aₙ = aₙ₋₁ + aₙ₋₂ + aₙ₋₃

All recurrence relations can be solved using techniques involving characteristic equations and roots—the same techniques that give Binet's formula.

Properties of Fibonacci Numbers

Every third Fibonacci number is even. F₃ = 2, F₆ = 8, F₉ = 34, ...

Every fourth is divisible by 3. F₄ = 3, F₈ = 21, F₁₂ = 144, ...

Every fifth is divisible by 5. F₅ = 5, F₁₀ = 55, F₁₅ = 610, ...

In general, Fₘ divides Fₙ if and only if m divides n. The divisibility structure of position numbers mirrors the divisibility structure of the Fibonacci numbers themselves.

Sum of first n Fibonacci numbers: F₁ + F₂ + ... + Fₙ = Fₙ₊₂ - 1

Sum of squares: F₁² + F₂² + ... + Fₙ² = Fₙ · Fₙ₊₁

These aren't coincidences. They're consequences of how the recursive structure propagates.

Fibonacci in Algorithms

Computer scientists love Fibonacci because it's the simplest example of:

Recursive algorithms with overlapping subproblems. Computing F₁₀ naively means computing F₉ and F₈. But F₉ also needs F₈. This duplication explodes exponentially—the naive algorithm is terribly inefficient.

Dynamic programming. The fix is to store previously computed values. Compute F₁, F₂, F₃, ... in order, saving each result. Now F₁₀₀₀ is trivial.

Fibonacci teaches the core lesson of algorithm design: recursive solutions can be elegant but slow; clever caching makes them fast.

The Zeckendorf Representation

Every positive integer can be written as a sum of non-consecutive Fibonacci numbers, in exactly one way.

• 10 = 8 + 2 (F₆ + F₃)
• 17 = 13 + 3 + 1 (F₇ + F₄ + F₁)
• 100 = 89 + 8 + 3 (F₁₁ + F₆ + F₄)

You can never use adjacent Fibonacci numbers (like 8 and 5) because 8 + 5 = 13, which is itself a Fibonacci number.

This is Zeckendorf's theorem. It gives a Fibonacci-based number system analogous to binary.

Growth Rate

The Fibonacci sequence grows exponentially, with growth ratio approaching φ ≈ 1.618.

This is slower than doubling (ratio 2) but faster than any polynomial growth.

Key approximation: Fₙ ≈ φⁿ / √5 ≈ 0.447 × 1.618ⁿ

The approximation is exact to the nearest integer.

Why Fibonacci Matters

1. It's the simplest recursive sequence. Understanding Fibonacci means understanding how backward-looking rules generate forward-growing patterns.
2. It connects to the golden ratio. The ratio of consecutive terms converges to φ, linking discrete mathematics to geometry and aesthetics.
3. It appears in nature. Not because nature knows math, but because the optimization problems nature solves have Fibonacci-structured solutions.
4. It teaches algorithmic thinking. Fibonacci is the canonical example for understanding recursion, memoization, and dynamic programming.
5. It has beautiful identities. The sum formulas, divisibility patterns, and Zeckendorf representation reveal deep structure.

The Fibonacci sequence says: when growth depends on where you've been, elegant patterns emerge. Look backward to understand what comes next.

Part 4 of the Sequences Series series.

Previous: Geometric Sequences: Multiplying by the Same Factor Next: Sigma Notation: Writing Sums Compactly