A recurrence relation defines each term of a sequence in terms of one or more previous terms, together with specified starting values. The Fibonacci sequence — where each number is the sum of the two before it — is the most famous example, but recurrence relations appear throughout combinatorics, algorithm analysis, and the modelling of populations, finances, and recursive computer programs.
The Fibonacci sequence begins 1, 1, 2, 3, 5, 8, 13, 21, .... Notice the pattern: each number is simply the sum of the two numbers immediately before it (1+1=2, 1+2=3, 2+3=5, and so on). This rule — defining each term using earlier terms — is called a recurrence relation. It doesn't give you a direct formula for, say, the 100th term; instead, it gives you a rule for building each new term step by step from what came before.
While a recurrence relation is easy to state, actually computing a specific faraway term (like the 1000th Fibonacci number) by working through the rule one step at a time can be slow. Mathematicians have developed systematic techniques for converting many recurrence relations into direct, closed-form formulas that can compute any specific term immediately, without needing to calculate every earlier term first.
A linear recurrence relation expresses each term as a linear combination of a fixed number of preceding terms. The Fibonacci recurrence, Fₙ=Fₙ₋₁+Fₙ₋₂, is a linear recurrence of "order 2" (depending on the two previous terms). Such relations can be systematically solved using a standard technique: guess a solution of the form Fₙ=rⁿ, substitute into the recurrence, and solve the resulting polynomial ("characteristic equation") for r.
Substituting Fₙ=rⁿ into Fₙ=Fₙ₋₁+Fₙ₋₂ gives r²=r+1 — precisely the defining equation of the golden ratio φ (see that entry)! The two roots of this characteristic equation are φ=(1+√5)/2 and its conjugate ψ=(1−√5)/2. The general solution is a combination Fₙ=Aφⁿ+Bψⁿ, and using the known starting values F₁=1, F₂=1 to solve for A and B yields the closed-form Binet's formula:
Remarkably, though this formula involves the irrational numbers φ, ψ, and √5 throughout, it always evaluates to an exact whole number for every positive integer n — a striking and initially surprising fact.
Recursive algorithms (see the Big-O Notation entry) naturally give rise to recurrence relations describing their running time. Merge sort's running time satisfies T(n) = 2T(n/2) + O(n) — splitting the problem into two half-sized subproblems, plus linear-time work to combine the results. Solving this particular recurrence (via the widely-used Master Theorem, a general tool for solving this common family of "divide and conquer" recurrences) yields T(n) = O(n log n), directly explaining merge sort's well-known efficiency.
Not all recurrences are linear. The logistic map, xₙ₊₁ = rxₙ(1−xₙ), is a simple-looking non-linear recurrence used to model constrained population growth — and, depending on the parameter r, it exhibits everything from simple stable behaviour to full mathematical chaos (see the Differential Equation entry for the closely related continuous case).
As introduced in the Combinatorics entry, a generating function encodes an entire sequence as the coefficients of a formal power series. Recurrence relations translate directly into algebraic equations involving the generating function itself — for the Fibonacci recurrence, defining G(x)=ΣFₙxⁿ and substituting the recurrence relation yields G(x) = x/(1−x−x²), a compact closed-form expression from which Binet's formula (and much else about the sequence's properties) can be systematically extracted using partial fraction decomposition and other standard algebraic techniques.
For a recurrence of the standard "divide and conquer" form T(n) = aT(n/b) + f(n), the Master Theorem provides a direct classification of the solution's growth rate based on comparing f(n) against n^(log_b a): if f(n) grows slower, T(n) = Θ(n^(log_b a)); if comparably, an extra logarithmic factor appears; if faster (subject to a technical regularity condition), T(n) = Θ(f(n)). This single, general result immediately resolves the running-time analysis for an enormous range of common recursive divide-and-conquer algorithms without requiring an ad-hoc, from-scratch derivation for each individual case.
Recurrence-like reasoning in mathematics is genuinely ancient: the Fibonacci sequence itself appears in Indian prosody (the study of Sanskrit poetic meter) centuries before Fibonacci's famous 1202 CE European treatment — Piṅgala (c. 200 BCE) and later commentators including Virahāṅka (c. 600–800 CE) and Hemachandra (c. 1150 CE) studied essentially the identical recurrence in the context of systematically counting valid poetic syllable patterns of long and short sounds, independently of and considerably predating its more famous European namesake. Leonardo of Pisa ("Fibonacci") introduced the sequence to Europe in his 1202 book Liber Abaci, in the context of a hypothetical, deliberately simplified rabbit-population growth problem.
In theoretical computer science, recurrence relations underlie the systematic counting of strings satisfying specific structural pattern constraints (recognised by finite automata or generated by formal context-free grammars), connecting the elementary study of number sequences directly to the formal theory of computation and to compiler design and parsing theory in practical software engineering.