Recurrence Relations

A rigorous introduction to recursively defined sequences, initial conditions, iteration, and closed-form verification.

A recurrence builds each new state from earlier states and a starting condition. A chain of indexed boxes feeds previous values into the next one. A base-case anchor prevents the backward dependency from continuing indefinitely.

Precise definition

A recurrence relation defines sequence terms using earlier terms. An order-$k$ recurrence generally needs $k$ independent initial values to determine one sequence. A linear homogeneous constant-coefficient recurrence has the form $a_n=c_1a_{n-1}+\cdots+c_ka_{n-k}$; nonhomogeneous recurrences add a forcing term.

Notation and mathematical language

The index range matters: $a_n=3a_{n-1}$ for $n\ge1$ plus $a_0=2$ yields $a_n=2\cdot3^n$. A closed form gives $a_n$ directly as a function of $n$. For $a_n=ra_{n-1}$, repeated substitution produces a geometric sequence.

Conceptual picture

A recurrence describes local evolution, while a closed form describes the term at any index without computing all predecessors. A computation tree can expose repeated work in a naive recursive algorithm; dynamic programming stores previously computed terms while preserving the same mathematical recurrence.

Fully worked example

Interpretation and application

Recurrences model compound growth, population generations, algorithm running times, and combinatorial structures. A recurrence is exact relative to its model; measured data may only approximately follow it, so model fit and causal interpretation require separate evidence.