Recurrence Relations

A recurrence defines each term from earlier ones, so two seed values plus one rule generate an entire sequence without any direct formula.

Each Fibonacci term sums its two parents, growing 1, 1, 2, 3, 5 to 8, so the whole sequence flows from two seeds and one rule

Why Does This Exist?

Many processes cannot see the future but remember the past: rabbit populations, running algorithm costs, recurrent network states, loan balances. Recurrence relations are the native language of such processes: each new value is a function of previous values. They describe dynamic programming costs, analyze recursive algorithms, and define the sequences (like Fibonacci) that appear in nature, art, and interview questions.

Their danger matches their power: a recurrence can explode, oscillate, or depend so sensitively on seeds that floating-point noise rewrites the answer. This page teaches the anatomy (rule plus seeds), the Fibonacci workhorse, and how to unroll safely. Time-based modeling with memory continues in recurrent architectures; growth analysis uses computational complexity.

The one idea you need first

A recurrence gives $a_n$ in terms of earlier terms, for example $a_n = 2a_{n-1} + 1$ , plus initial conditions (seeds) like $a_1 = 0$ that start the chain. Rule without seeds generates nothing; seeds without rule generate one step. Unrolling means applying the rule repeatedly to reach any term.

Think of It Like This

A recipe that references yesterday's soup

A soup kitchen rule says: today's soup equals yesterday's soup plus the day before's, with Monday and Tuesday starting at one pot each. Wednesday makes 2, Thursday 3, Friday 5. Nobody measures fresh; every pot descends from the two seeds through the rule.

Change Monday's pot and Friday changes too: history propagates. Skip recording a day and the chain breaks until re-anchored. The analogy stops at linearity: real recurrences can square, cap, or branch on conditions, while the soup only adds.

How It Actually Works

The Fibonacci recurrence, with $F_n$ the $n$ -th term:

F_n = F_{n-1} + F_{n-2}, \qquad F_1 = 1,\ F_2 = 1

In plain words: each term sums the previous two; the seeds $1, 1$ anchor the start. Unrolling builds $1, 1, 2, 3, 5, 8, 13, \ldots$ purely by addition. The order of a recurrence is how far back it reaches (Fibonacci is second-order). Linear recurrences with constant coefficients admit closed forms: Fibonacci's is Binet's formula with the golden ratio $\phi \approx 1.618$ , and $F_n$ grows like $\phi^n$ , exponentially.

Solving in general means finding that closed form or bound: guess patterns for first-order linear rules ( $a_n = r a_{n-1}$ gives $a_1 r^{n-1}$ , the geometric sequence), use characteristic equations for higher orders, or unroll-and-bound for algorithm analysis.

Worked example

Unroll Fibonacci to the sixth term and verify the growth claim:

Seeds: $F_1 = 1$ , $F_2 = 1$ .
$F_3 = 1 + 1 = 2$ ; $F_4 = 1 + 2 = 3$ ; $F_5 = 2 + 3 = 5$ ; $F_6 = 3 + 5 = 8$ .
Check ratios: $5/3 \approx 1.667$ , $8/5 = 1.6$ , closing toward $\phi \approx 1.618$ from both sides.

Six terms from two seeds and one addition rule. The ratio check confirms the exponential character without solving anything: successive quotients already whisper the golden ratio.

Code

Unroll iteratively and confirm against the closed-form growth rate.

1fib = [1, 1]2for _ in range(4):3    fib.append(fib[-1] + fib[-2])  # each term sums its two parents4print(fib)                         # -> [1, 1, 2, 3, 5, 8]5print(round(fib[-1] / fib[-2], 4))  # -> 1.6

Terms $[1, 1, 2, 3, 5, 8]$ with ratio $1.6$ approaching $1.618$ : unrolling and theory agree.

Watch Out For

Recomputing shared subterms exponentially

A naive recursive fib(n) calls itself twice per level, recomputing $F_{k}$ exponentially many times: fib(35) makes millions of calls for 35 answers. The recurrence defines the values; it does not mandate the computation strategy.

Compute bottom-up (loop) or memoize: each term once, linear time. If a recursive function is mysteriously slow on small inputs, overlapping subproblems are the prime suspect.

Seeds that look interchangeable but are not

$F_1 = 1, F_2 = 1$ versus $F_1 = 1, F_2 = 2$ (Lucas-like) produce different sequences from the identical rule: $1, 1, 2, 3, 5$ versus $1, 2, 3, 5, 8$ . Code that hardcodes the rule but takes seeds "from config" silently generates a different sequence when the config drifts.

Test seeds explicitly alongside the rule. If a sequence is shifted or scaled versus expectation, diff the first two values before suspecting the recurrence.

The Quick Version

Recurrences define each term from earlier ones; seeds start the chain.
Fibonacci: $F_n = F_{n-1} + F_{n-2}$ with $1, 1$ gives $1, 1, 2, 3, 5, 8$ .
Successive ratios approach the golden ratio $1.618$ : exponential growth.
First-order linear recurrences unroll into geometric sequences.
Compute bottom-up or memoized, never naive doubly-recursive.
Seeds are load-bearing: same rule with different seeds is a different sequence.