Recurrence Relations and Solving Them

A recurrence relation defines each term of a sequence as a function of preceding terms. Solving one means finding a closed-form expression $a_{n}$ depending only on $n$ . The dominant techniques are characteristic equations (linear constant-coefficient), generating functions, iteration/telescoping, and the Master Theorem (divide-and-conquer). Indispensable in combinatorics, algorithm analysis, numerical methods, and discrete dynamical systems. Studied since Fibonacci (1202), formalized by de Moivre, Euler, and Laplace in the 18th century.

A recurrence relation is an equation expressing the $n$ -th term of a sequence $(a_{n})$ in terms of one or more earlier terms, together with a finite set of initial conditions that pin down the sequence uniquely. They matter because vast classes of counting problems, algorithmic runtimes, and discretized differential equations are naturally recursive — the recurrence is often easier to write down than the answer. The art lies in converting the recursive description into a closed form so that $a_{n}$ can be computed in $O (1)$ rather than $O (n)$ steps, and so that asymptotic behavior is transparent. A surprising fact: the same linear recurrence governs the Fibonacci numbers and the convergents of the simplest continued fraction, and its solution involves the golden ratio $φ$ — an irrational number generating a sequence of integers.

The Core Insight

A recurrence is a discrete dynamical rule; solving it is finding the rule's "flow." For linear constant-coefficient recurrences the key realization is that geometric sequences $a_{n} = r^{n}$ are eigenfunctions of the shift operator — substituting $r^{n}$ turns the recurrence into a polynomial (the characteristic equation), and superposition assembles the general solution from these geometric building blocks. Every other method (generating functions, matrix powers, Z-transforms) is a repackaging of this single idea.

Formal Statement

Recurrence Relation of Order k

A recurrence relation of order $k$ for a sequence $(a_{n})_{n \geq 0}$ is an equation

a_{n} = F (n, a_{n - 1}, a_{n - 2}, \dots, a_{n - k}), n \geq k,

⟳this is a definition —

F

is any given function and "order

k

" means the term reaches back exactly

k

steps, requiring

a_{n - k}

to genuinely appear.

together with initial conditions $a_{0}, a_{1}, \dots, a_{k - 1}$ . Here $n$ is the integer index, $a_{n}$ the term, $k$ the order, and $F$ the recurrence function. The recurrence is:

linear if $F$ is affine in the $a_{n - i}$ ;
homogeneous if the constant (forcing) term is zero;
constant-coefficient if the coefficients do not depend on $n$ .

Linear Homogeneous Recurrence with Constant Coefficients (LHRCC)

A linear homogeneous recurrence with constant coefficients of order $k$ has the form

a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k}, c_{k} \neq = 0,

⟳specialize [1] to

F

linear, no

n

-dependence in coefficients, and zero constant term;

c_{k} \neq = 0

enforces true order

k

with constants $c_{1}, \dots, c_{k} \in C$ . Its characteristic equation is the degree- $k$ polynomial obtained by substituting the trial solution $a_{n} = r^{n}$ :

r^{k} - c_{1} r^{k - 1} - c_{2} r^{k - 2} - \dots - c_{k} = 0.

⟳substitute

a_{n} = r^{n}

into [2], giving

r^{n} = c_{1} r^{n - 1} + \dots + c_{k} r^{n - k}

; divide by

r^{n - k}

and rearrange.

General Solution via Characteristic Roots

Let [2] have characteristic equation [3] with distinct roots $r_{1}, \dots, r_{t}$ of multiplicities $m_{1}, \dots, m_{t}$ where $\sum m_{j} = k$ . Then every solution of [2] is uniquely

a_{n} = j = 1 \sum t (α_{j, 0} + α_{j, 1} n + \dots + α_{j, m_{j} - 1} n^{m_{j} - 1}) r_{j}^{n},

⟳each root

r_{j}

contributes

m_{j}

linearly independent solutions

n^{p} r_{j}^{n}

for

p = 0, \dots, m_{j} - 1

; the

k

constants

α_{j, p}

are fixed by the

k

initial conditions through a Vandermonde-type system that is invertible because the roots are distinct.

where the $α_{j, p}$ are constants determined by the initial conditions.

Particular + Homogeneous Decomposition (Inhomogeneous Case)

For the inhomogeneous linear recurrence

a_{n} = c_{1} a_{n - 1} + \dots + c_{k} a_{n - k} + g (n),

⟳this is [2] plus a forcing term

g (n)

the general solution is

a_{n} = a_{n}^{(h)} + a_{n}^{(p)},

⟳linearity — if

a^{(p)}

solves [5] and

a^{(h)}

solves the associated homogeneous [2], their sum solves [5]; conversely the difference of any two solutions of [5] satisfies [2].

where $a_{n}^{(h)}$ is the general homogeneous solution [4] and $a_{n}^{(p)}$ is any particular solution. When $g (n) = b^{n} p (n)$ with $p$ a polynomial of degree $d$ , try

a_{n}^{(p)} = n^{s} b^{n} q (n),

⟳

q

is a degree-

d

polynomial with undetermined coefficients;

s

is the multiplicity of

b

as a root of [3] (the factor

n^{s}

avoids collision/resonance with homogeneous solutions, exactly as in linear ODEs).

Why It Holds / Derivation

proof[Solution Space is k-Dimensional; Geometric Basis] Step 1 — The solution set is a vector space. If $(a_{n})$ and $(b_{n})$ both satisfy the homogeneous [2], so does $λ a_{n} + μ b_{n}$ for scalars $λ, μ$ , since [2] is linear and homogeneous. Thus solutions form a $C$ -vector space $V$ .

Step 2 — $dim V = k$ . A solution is completely determined by the initial vector

(a_{0}, \dots, a_{k - 1})

via forward iteration of [2], and conversely each such vector yields a solution. The map

V \to C^{k}

(a_{n}) \mapsto (a_{0}, \dots, a_{k - 1})

, is a linear bijection, so

dim V = k

. Step 3 — Geometric sequences are solutions. Substituting

a_{n} = r^{n}

into [2] and dividing by

r^{n - k}

yields the characteristic equation [3]. Hence

r^{n}

solves [2] iff

r

is a characteristic root. Step 4 — Distinct roots give a basis. If

r_{1}, \dots, r_{k}

are distinct, the sequences

(r_{1}^{n}), \dots, (r_{k}^{n})

are linearly independent: their initial-condition vectors form the columns of a Vandermonde matrix with determinant

\prod_{i < j} (r_{j} - r_{i}) \neq = 0

. These

k

independent solutions span the

k

-dimensional

V

. Step 5 — Repeated roots. If

r

has multiplicity

m

, then

r

is a root of [3] and its first

m - 1

derivatives. One checks that

n^{p} r^{n}

for

p = 0, \dots, m - 1

each satisfy [2] (substitute and use

\frac{d ^{p}}{d r ^{p}}

of the characteristic polynomial vanishing at

r

). These supply

m

independent solutions per repeated root, restoring a total of

k

, hence the form [4].

■

Abraham de Moivre | 1667–1754

De Moivre, a French Huguenot émigré to London and friend of Newton, was the first to give a systematic closed-form solution of linear recurrences. In Miscellanea Analytica (1730) he introduced what we now call generating functions to solve "recurrent series," explicitly producing the Fibonacci closed form before Binet's name attached to it. His work on the de Moivre formula $(cos θ + i sin θ)^{n} = cos n θ + i sin n θ$ is precisely the complex-root machinery needed to express oscillatory solutions of real recurrences in trigonometric form. He famously, and morbidly, predicted his own death by noticing he was sleeping 15 more minutes each night — an arithmetic recurrence terminating when total sleep reached 24 hours.

Building Intuition

Think of a recurrence as a machine with $k$ memory slots. At each tick it reads the last $k$ values, combines them, and pushes out a new value. The whole future is locked once you load the initial $k$ values — exactly $k$ degrees of freedom, which is why you need exactly $k$ initial conditions and the solution space is $k$ -dimensional.

Why geometric sequences? The recurrence is invariant under shifting $n$ : the rule at step $100$ is identical to the rule at step $5$ . A sequence that "looks the same after shifting except for scaling" is geometric, $a_{n + 1} / a_{n} = r$ . These self-similar sequences are the natural modes, like normal modes of a vibrating system. The characteristic equation just asks "which scaling factors $r$ are consistent with the rule?" Repeated roots are the discrete echo of critical damping: when two modes collide they fuse and a factor of $n$ appears, exactly as $t e^{r t}$ appears for repeated ODE roots.

Fibonacci growth: integer terms tracking the golden-ratio mode $\varphi^n$

Worked Examples

Fibonacci — Distinct Roots

Given:

a_{n} = a_{n - 1} + a_{n - 2}

, with

a_{0} = 0, a_{1} = 1

. Step 1 — Characteristic equation. Substitute

a_{n} = r^{n}

r^{2} = r + 1

, i.e.

r^{2} - r - 1 = 0

. Step 2 — Roots.

r = \frac{1 \pm 5}{2}, φ = \frac{1 + 5}{2} \approx 1.618, ψ = \frac{1 - 5}{2} \approx - 0.618.

Step 3 — General solution.

a_{n} = α φ^{n} + β ψ^{n}

(distinct roots). Step 4 — Apply initial conditions.

$n = 0$ : $α + β = 0$ .
$n = 1$ : $α φ + β ψ = 1$ .

Solving: $α = 1/ 5, β = - 1/ 5$ .

Step 5 — Closed form (Binet's formula).

a_{n} = \frac{φ ^{n} - ψ ^{n}}{5}

Check:

a_{5} = (φ^{5} - ψ^{5}) / 5 = (11.0902 - (- 0.0902)) /2.236 = 5.

✓ (dimensionless count of pairs/tilings)

Inhomogeneous with Resonance — Algorithm Cost

Given: the cost recurrence

T_{n} = 2 T_{n - 1} + 3 \cdot 2^{n}

, with

T_{0} = 1

. (Forcing

g (n) = 3 \cdot 2^{n}

.) Step 1 — Homogeneous part.

r - 2 = 0 \Rightarrow r = 2

, so

T_{n}^{(h)} = A \cdot 2^{n}

. Step 2 — Detect resonance. The forcing base

b = 2

equals the homogeneous root, multiplicity

s = 1

. By [7] try

T_{n}^{(p)} = C n 2^{n}

(note the factor

n

). Step 3 — Solve for $C$ . Substitute into the recurrence:

C n 2^{n} = 2 (C (n - 1) 2^{n - 1}) + 3 \cdot 2^{n} = C (n - 1) 2^{n} + 3 \cdot 2^{n} .

Divide by

2^{n}

C n = C (n - 1) + 3 \Rightarrow C = 3.

T_{n}^{(p)} = 3 n 2^{n}

. Step 4 — General + initial condition.

T_{n} = A \cdot 2^{n} + 3 n 2^{n}

. At

n = 0

T_{0} = A = 1

, so

A = 1

. Step 5 — Closed form.

T_{n} = (1 + 3 n) 2^{n}

Check:

T_{1} = 2 (1) + 3 \cdot 2 = 8

, and formula gives

(1 + 3) \cdot 2 = 8.

✓ Asymptotically

T_{n} = Θ (n 2^{n})

operations.

Common Misconceptions

Resonance: forgetting the factor $n^s$

The single most common error in the inhomogeneous case is using a trial solution that collides with a homogeneous solution. If $g (n) = b^{n} p (n)$ and $b$ is a characteristic root of multiplicity $s$ , you must multiply the trial form by $n^{s}$ (equation [7]). Forgetting this gives an inconsistent system with no solution for the undetermined coefficients, because you are trying to match a forcing term using a function the operator annihilates. This is the exact discrete analogue of resonance in driven oscillators.

Wrong number of initial conditions

An order- $k$ recurrence needs exactly $k$ initial conditions, and they must be "consecutive enough" to determine the solution. Supplying $a_{0}$ and $a_{2}$ for a second-order recurrence may fail (or be ill-posed) if the resulting linear system is singular. Too few conditions leaves free parameters; too many overdetermines and may be inconsistent.

Geometric ansatz fails for repeated roots

Consider $a_{n} = 4 a_{n - 1} - 4 a_{n - 2}$ with $a_{0} = 1, a_{1} = 4$ . Characteristic equation $r^{2} - 4 r + 4 = (r - 2)^{2} = 0$ gives a double root $r = 2$ . If you naively write $a_{n} = (α + β) 2^{n} = C \cdot 2^{n}$ , you have only one free constant and cannot match both initial conditions: $C = 1$ from $a_{0}$ , but then $a_{1} = 2 \neq = 4$ . The fix is the repeated-root form $a_{n} = (α + β n) 2^{n}$ . Then $α = 1$ , and $(α + β) \cdot 2 = 4 \Rightarrow β = 1$ , giving $a_{n} = (1 + n) 2^{n}$ . The "extra" $n$ is not optional — it is forced by the dimension count in [4].

Connections

Recurrence relations are the discrete sibling of Linear Differential Equations: the characteristic-equation method, superposition, and resonance all transfer verbatim, with $r^{n}$ playing the role of $e^{λ t}$ . The matrix viewpoint links them to Eigenvalues and Eigenvectors — a linear recurrence is $v_{n} = A v_{n - 1}$ on the state vector $(a_{n}, \dots, a_{n - k + 1})$ , so $a_{n}$ is read off from $A^{n}$ , and eigenvalues are exactly the characteristic roots. Generating Functions provide an algebraic alternative that handles inhomogeneous and variable-coefficient cases uniformly by encoding the whole sequence as a power series. The Z-Transform in signal processing is the engineering name for the same generating-function map. Finally, the Master Theorem specializes the theory to divide-and-conquer recurrences central to Analysis of Algorithms.

Real-World Applications

Algorithm analysis (Merge Sort, Karatsuba, FFT). Divide-and-conquer runtimes obey $T (n) = a T (n / b) + f (n)$ ; the Master Theorem yields $T (n) = Θ (n lo g n)$ for merge sort ( $a = b = 2$ ) and $Θ (n^{1.585})$ for Karatsuba multiplication.
Compound interest & amortization. A loan balance satisfies $B_{n} = (1 + i) B_{n - 1} - P$ , an inhomogeneous first-order recurrence whose closed form gives the standard mortgage payment formula.
Population & epidemiology (Leslie matrices). Age-structured population growth $n_{t + 1} = L n_{t}$ is a vector recurrence; the dominant eigenvalue of $L$ is the asymptotic growth rate.
Digital signal processing (IIR filters). Infinite-impulse-response filters are literally recurrences $y_{n} = \sum b_{i} x_{n - i} - \sum a_{j} y_{n - j}$ ; stability requires all characteristic roots inside the unit circle.
Numerical methods (Newton, finite differences). Iterative root-finding and discretized PDEs produce recurrences; their stability is the boundedness of the homogeneous solution.
Combinatorics (Catalan numbers, derangements, tilings). Counting binary trees, balanced parentheses, or domino tilings reduces to solving recurrences like $C_{n} = \sum C_{i} C_{n - 1 - i}$ .
Computer graphics & fractals. Subdivision schemes and L-systems generate geometry by recurrent refinement rules.

Historical Development

1202 — Leonardo of Pisa (Fibonacci), Liber Abaci, poses the rabbit-breeding problem, introducing the Fibonacci recurrence to the West.
1718–1730 — Abraham de Moivre develops generating functions ("recurrent series") and solves linear recurrences in closed form, deriving Binet's formula a century before Binet.
1748 — Leonhard Euler, Introductio in Analysin Infinitorum, systematizes generating functions and the characteristic-equation method, treating repeated roots.
1759 — Joseph-Louis Lagrange advances the theory of linear difference equations and their connection to interpolation.
1812 — Pierre-Simon Laplace, Théorie analytique des probabilités, develops the generating-function calculus extensively (the "Laplace/Z-transform" lineage) for probabilistic recurrences.
1843 — Jacques Philippe Marie Binet publishes the eponymous Fibonacci formula, cementing the name.
1880s — Henri Poincaré studies asymptotics of solutions to linear recurrences with variable coefficients (Poincaré–Perron theory).
1960s — Rise of computer science reframes recurrences as runtime analysis; the Master Theorem emerges in algorithm textbooks.
1980 — Jon Bentley, Dorothea Haken, and James Saxe formalize and popularize the modern Master Theorem for divide-and-conquer recurrences.

Subtleties & Limits

The clean theory covers linear constant-coefficient recurrences. Beyond this:

Variable coefficients $a_{n} = c_{1} (n) a_{n - 1} + \dots$ rarely have elementary closed forms; the Poincaré–Perron theorem gives only asymptotic ratios $a_{n + 1} / a_{n} \to$ a root of a limiting characteristic equation, and even deciding whether a closed form exists (the algorithmic theory of holonomic / P-recursive sequences, via Petkovšek's algorithm) is delicate.
Nonlinear recurrences (e.g. the logistic map $x_{n + 1} = μ x_{n} (1 - x_{n})$ ) generically have no closed form and exhibit chaos; their study belongs to dynamical systems, not algebra.
Existence of "nice" closed forms is itself subtle: Gosper's and Zeilberger's algorithms (creative telescoping) decide hypergeometric summation but leave many sequences provably without elementary closed form.
Whether certain combinatorially natural sequences are P-recursive remains open in specific cases, an active research frontier in enumerative combinatorics.