Recurrence Relations — Homogeneous and Particular Solutions

A linear recurrence relation with constant coefficients is solved by combining the homogeneous solution (general solution of the equation with zero forcing term) and a particular solution (any single solution of the full equation). The general solution is $a_{n} = a_{n}^{(h)} + a_{n}^{(p)}$ . Applies to sequences defined recursively — algorithm analysis, combinatorics, difference equations, discrete dynamical systems. The method mirrors that for linear ODEs and dates to Euler, de Moivre, and Lagrange (18th century).

A recurrence relation expresses each term of a sequence $a_{n}$ as a function of earlier terms. A linear recurrence with constant coefficients has the form $a_{n} + c_{1} a_{n - 1} + \dots + c_{k} a_{n - k} = f (n)$ , where the $c_{i}$ are constants and $f (n)$ is a known forcing function. Such equations are the discrete analogues of linear differential equations, and they matter because they describe the cost of recursive algorithms, count combinatorial structures, and model population and economic dynamics. The central structural fact — surprisingly clean — is that the entire solution set is an affine space: take any particular solution and add every solution of the associated homogeneous equation. The most surprising practical consequence is that an apparently mysterious closed form (like Binet's formula for Fibonacci numbers, full of irrational $5$ ) emerges purely from the roots of a single polynomial.

The Core Insight

The solution operator is linear. If $L [a_{n}] = a_{n} + c_{1} a_{n - 1} + \dots + c_{k} a_{n - k}$ , then $L$ is a linear map on sequences. Solving $L [a_{n}] = f (n)$ is therefore exactly like solving a linear system $Lx = b$ : the solution set is a coset of the kernel. The kernel is the homogeneous solution space ( $L [a_{n}] = 0$ ), and any single solution of $L [a_{n}] = f (n)$ shifts the whole kernel into place. Everything else — characteristic equations, repeated-root corrections, the method of undetermined coefficients — is machinery for computing these two pieces.

Formal Statement

Linear Recurrence with Constant Coefficients

A $k$ -th order linear recurrence relation with constant coefficients is

a_{n} + c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k} = f (n), n \geq k,

where:

$a_{n}$ is the unknown sequence (the solution);
$c_{1}, \dots, c_{k}$ are real (or complex) constants with $c_{k} \neq = 0$ (so the order is genuinely $k$ );
$f (n)$ is a given forcing function (or nonhomogeneous term);
$k$ initial conditions $a_{0}, a_{1}, \dots, a_{k - 1}$ pin down a unique solution.

If $f (n) \equiv 0$ , the recurrence is homogeneous; otherwise it is nonhomogeneous (or inhomogeneous).

⟳This is the most general form invariant under the shift operator with fixed coefficients; the condition

c_{k} \neq = 0

guarantees that knowing

a_{n - 1}, \dots, a_{n - k}

determines

a_{n}

and that the past is recoverable.

Characteristic Equation

Substituting the trial solution $a_{n} = r^{n}$ into the homogeneous version of [1] and dividing by $r^{n - k}$ gives the characteristic equation

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

Its roots $r_{1}, \dots, r_{k}$ (with multiplicity) generate the homogeneous solution space.

⟳With

a_{n} = r^{n}

, each term

a_{n - j} = r^{n - j}

; factor out the lowest power

r^{n - k}

from

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

Structure of the General Solution

Let $a_{n}^{(p)}$ be any particular solution of the nonhomogeneous recurrence [1], and let $a_{n}^{(h)}$ denote the general solution of the associated homogeneous recurrence $L [a_{n}] = 0$ . Then every solution of [1] is

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

and conversely every sequence of this form solves [1]. The free constants in $a_{n}^{(h)}$ are fixed uniquely by the $k$ initial conditions.

⟳If

a_{n}

and

\tilde{a}_{n}

both solve

L [\cdot] = f

, linearity gives

L [a_{n} - \tilde{a}_{n}] = f - f = 0

, so their difference is homogeneous.

Homogeneous Solution from Roots

Let $r_{1}, \dots, r_{m}$ be the distinct roots of [2] with multiplicities $μ_{1}, \dots, μ_{m}$ ( $\sum μ_{i} = k$ ). Then the general homogeneous solution is

a_{n}^{(h)} = i = 1 \sum m (A_{i, 0} + A_{i, 1} n + \dots + A_{i, μ_{i} - 1} n^{μ_{i} - 1}) r_{i}^{n},

with $k$ arbitrary constants $A_{i, j}$ . For a simple root this reduces to $A_{i} r_{i}^{n}$ .

⟳Distinct-root solutions

r_{i}^{n}

are linearly independent (Vandermonde). For a root of multiplicity

μ

, the functions

n^{j} r^{n}

(

0 \leq j < μ

) all lie in the kernel; verify by substituting

a_{n} = n r^{n}

for a double root.

Why It Holds / Derivation

General Solution Structure

We prove [3] in numbered steps.

$L$ is linear. Define $L [a]_{n} = a_{n} + c_{1} a_{n - 1} + \dots + c_{k} a_{n - k}$ . For scalars $α, β$ and sequences $a, b$ :

L [α a + β b]_{n} = α L [a]_{n} + β L [b]_{n} .

⟳Each term

(α a + β b)_{n - j} = α a_{n - j} + β b_{n - j}

; sum termwise.

Difference of two solutions is homogeneous. Suppose $L [a] = f$ and $L [\tilde{a}] = f$ . By step 1, $L [a - \tilde{a}] = f - f = 0$ , so $h := a - \tilde{a}$ solves the homogeneous equation.

Therefore $a = \tilde{a} + h = a^{(p)} + a^{(h)}$ . Every solution differs from a fixed particular solution by a homogeneous solution.

Conversely, if $h$ is homogeneous and $a^{(p)}$ particular, then $L [a^{(p)} + h] = L [a^{(p)}] + L [h] = f + 0 = f$ , so the sum is a solution.

Dimension count. The map "solution $\mapsto (a_{0}, \dots, a_{k - 1})$ " is a bijection between the homogeneous solution space and $R^{k}$ (or $C^{k}$ ), because initial data determine and are determined freely. Hence the kernel has dimension $k$ , matching the $k$ constants in [4]. $■$

Repeated-Root Solutions

Suppose $r$ is a double root of [2], so the characteristic polynomial $P (r)$ satisfies $P (r) = P^{'} (r) = 0$ . Consider the operator-level identity: applying $L$ to $r^{n}$ produces $P (r) r^{n - k}$ . Differentiating $r^{n}$ with respect to $r$ before applying $L$ commutes appropriately, giving

L [n r^{n - 1}] = \frac{d}{d r} (P (r) r^{n - k}) = P^{'} (r) r^{n - k} + P (r) (n - k) r^{n - k - 1} .

At a double root both $P (r) = 0$ and $P^{'} (r) = 0$ , so the right side vanishes; thus $n r^{n}$ (a constant multiple of $n r^{n - 1}$ ) is also a homogeneous solution. Iterating differentiation gives $n^{j} r^{n}$ for $j < μ$ . $■$

⟳Treat

r^{n}

as a function of the continuous variable

r

;

L

acts only on the index

n

, so

\partial_{r}

passes through it.

Abraham de Moivre | 1667–1754

De Moivre, a French Huguenot émigré in London, was the first to systematically extract closed forms from recurrences. Studying the Fibonacci-like sequences arising in probability (gambler's ruin, runs in coin tossing), he introduced the generating-function idea and the trick of solving $a_{n} = a_{n - 1} + a_{n - 2}$ via roots of $x^{2} = x + 1$ . The resulting expression $a_{n} = \frac{ϕ ^{n} - ψ ^{n}}{5}$ — later named Binet's formula after the 19th-century mathematician who popularized it — was effectively known to de Moivre and to Euler. De Moivre's Doctrine of Chances (1718, 1738, 1756) treats "recurring series" as a named topic, establishing the partial-fraction method for their summation.

Building Intuition

Think of a recurrence as a discrete machine that, given enough past states, computes the next. The homogeneous part captures the machine's internal dynamics — how it would evolve if left alone (geometric growth/decay, oscillation), governed entirely by the roots $r_{i}$ . The roots are the machine's natural modes: $∣ r ∣ > 1$ means a mode blows up, $∣ r ∣ < 1$ means it dies, $∣ r ∣ = 1$ means it persists, and complex roots mean it oscillates.

The particular solution is the machine's forced response — the way it tracks the external input $f (n)$ . After transients (the decaying homogeneous modes) wash out, the particular solution dominates, just as a driven oscillator eventually moves at the driving frequency. The two pieces are independent because the system is linear: superposition lets you solve "natural behavior" and "forced behavior" separately and simply add them.

Root locations in the complex plane and their dynamical meaning for $a_n^{(h)}=A r^n$

Worked Examples

Fibonacci — Homogeneous, Distinct Roots

Given:

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

, with

a_{0} = 0

a_{1} = 1

. (Forcing

f (n) = 0

, so it is purely homogeneous.) Step 1 — Characteristic equation. Rewrite as

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

. Trial

a_{n} = r^{n}

r^{2} - r - 1 = 0.

⟳divide

r^{n} - r^{n - 1} - r^{n - 2} = 0

r^{n - 2}

Step 2 — Roots.

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

⟳quadratic formula on [7].

Step 3 — General homogeneous solution. Distinct roots, so

a_{n} = A ϕ^{n} + B ψ^{n}

. Step 4 — Apply initial conditions.

{A + B = 0 A ϕ + B ψ = 1 \Rightarrow A = \frac{1}{5}, B = - \frac{1}{5} .

⟳

n = 0

gives the first;

n = 1

the second; subtract using

ϕ - ψ = 5

Answer:

a_{n} = \frac{ϕ ^{n} - ψ ^{n}}{5} (Binet’s formula; dimensionless count)

Check:

a_{5} = \frac{11.09 - ( - 0.09 )}{2.236} = 5

. ✓

Nonhomogeneous — Repeated Root + Polynomial Forcing

Given:

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

, with

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

. Step 1 — Homogeneous part. Characteristic equation

r^{2} - 4 r + 4 = (r - 2)^{2} = 0

, a double root

r = 2

. By [4]:

a_{n}^{(h)} = (A + B n) 2^{n} .

⟳multiplicity 2 introduces the factor

n

Step 2 — Particular solution (undetermined coefficients). Forcing

f (n) = 3 n

is linear and

r = 1

is not a root, so try

a_{n}^{(p)} = α n + β

. Substitute:

(α n + β) - 4 (α (n - 1) + β) + 4 (α (n - 2) + β) = 3 n .

⟳shift the index in each occurrence and collect.

Expanding: $α n + β - 4 α n + 4 α - 4 β + 4 α n - 8 α + 4 β = α n + (- 4 α + β)$ . Matching:

α = 3, - 4 α + β = 0 \Rightarrow β = 12.

a_{n}^{(p)} = 3 n + 12

⟳coefficient of

n

gives

α = 3

; constant term gives

β = 4 α

Step 3 — General solution.

a_{n} = (A + B n) 2^{n} + 3 n + 12

. Step 4 — Initial conditions.

{n = 0 : A + 12 = 1 \Rightarrow A = - 11 n = 1 : 2 (A + B) + 15 = 2 \Rightarrow A + B = - \frac{13}{2} \Rightarrow B = \frac{9}{2}

⟳plug

n = 0, 1

into the full general solution and solve the

2 \times 2

system.

Answer:

a_{n} = (- 11 + \frac{9}{2} n) 2^{n} + 3 n + 12 (dimensionless)

Check

a_{2}

(- 11 + 9) \cdot 4 + 6 + 12 = - 8 + 18 = 10

; directly

a_{2} = 4 a_{1} - 4 a_{0} + 6 = 8 - 4 + 6 = 10

. ✓

Common Misconceptions

Resonance: the forcing matches a homogeneous mode. When the trial particular solution duplicates a term already in

a_{n}^{(h)}

, the naive guess fails (it gets annihilated by

L

). You must multiply by $n^{s}$ , where

s

is the multiplicity of the offending root.

Concretely, for forcing $f (n) = b ρ^{n}$ :

a_{n}^{(p)} = {C ρ^{n} C n^{s} ρ^{n} ρ is not a characteristic root ρ is a root of multiplicity s .

⟳

L [ρ^{n}] = P (ρ) ρ^{n - k}

vanishes when

ρ

is a root; the factor

n^{s}

pushes you past the kernel just as in repeated-root homogeneous solutions.

Other frequent errors: (1) forgetting the $n$ -factors for repeated roots (you'll be one constant short and unable to satisfy all initial conditions); (2) applying initial conditions to $a_{n}^{(h)}$ before adding $a_{n}^{(p)}$ — always assemble the full $a_{n}$ first; (3) using $a_{n} = r^{n}$ on a recurrence whose coefficients are not constant (e.g. $a_{n} = n a_{n - 1}$ ) — the characteristic method does not apply there.

Solve $a_{n} - 3 a_{n - 1} = 2 \cdot 3^{n}$ . The homogeneous root is $r = 3$ , so $a_{n}^{(h)} = A 3^{n}$ . A student guesses $a_{n}^{(p)} = C 3^{n}$ . Substituting:

C 3^{n} - 3 \cdot C 3^{n - 1} = C 3^{n} - C 3^{n} = 0 \neq = 2 \cdot 3^{n} .

The guess is annihilated — it lives in the kernel. Because

ρ = 3

is a root of multiplicity

1

, the correct ansatz is

a_{n}^{(p)} = C n 3^{n}

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

Hence

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

. The "obvious" guess gave a contradiction precisely because of resonance.

Connections

Linear recurrences are the discrete shadow of Linear Differential Equations with Constant Coefficients: the shift operator $E$ (where $E a_{n} = a_{n + 1}$ ) plays the role of $\frac{d}{d t}$ , and the characteristic polynomial is identical in spirit. The homogeneous/particular split is the same affine-coset structure seen in any Linear Systems of Equations ( $Lx = b$ ). Generating Functions give an alternative, often more powerful, solution route — encoding a sequence as $\sum a_{n} x^{n}$ converts the recurrence into an algebraic equation whose partial-fraction expansion re-derives the root-based closed form. Higher-order recurrences also reduce to first-order vector recurrences $v_{n} = M v_{n - 1}$ , linking the topic to Eigenvalues and Eigenvectors: the characteristic roots $r_{i}$ are exactly the eigenvalues of the companion matrix $M$ , and repeated roots correspond to nontrivial Jordan Normal Form blocks.

Real-World Applications

Algorithm analysis. The running time of divide-and-conquer and recursive algorithms satisfies recurrences; e.g. naive recursive Fibonacci has call-count $T (n) = T (n - 1) + T (n - 2) + 1$ , solved by the same method (homogeneous $ϕ^{n}$ plus a constant particular solution).
Compound interest & amortized loans. A loan balance obeys $B_{n} = (1 + r) B_{n - 1} - P$ , with homogeneous mode $(1 + r)^{n}$ and particular (steady-state) solution $P / r$ ; the closed form gives the monthly-payment formula used by banks.
Population biology — Leslie matrices. Age-structured populations follow vector recurrences whose dominant eigenvalue (largest characteristic root) is the long-run growth rate.
Digital signal processing. IIR (infinite impulse response) filters are linear recurrences; their stability is exactly the condition that all characteristic roots lie inside the unit circle (the $∣ r ∣ < 1$ region in the diagram above).
Economics — multiplier-accelerator models. Samuelson's 1939 business-cycle model is a second-order recurrence whose complex roots produce damped oscillations of national income.
Numerical integration. Multistep methods (Adams–Bashforth, Adams–Moulton) propagate solutions via linear recurrences; zero-stability requires the characteristic roots' moduli to be $\leq 1$ .
Combinatorics. Counting tilings, lattice paths, binary strings avoiding patterns, and Catalan-type structures repeatedly yields linear recurrences solved by exactly this homogeneous + particular framework.

Historical Development

1202 — Leonardo of Pisa (Fibonacci), in Liber Abaci, poses the rabbit problem giving $F_{n} = F_{n - 1} + F_{n - 2}$ , the archetypal recurrence (though without a closed form).
1718 — Abraham de Moivre, Doctrine of Chances, introduces "recurring series" and the technique of summing them via roots of an auxiliary equation.
1748 — Leonhard Euler, Introductio in analysin infinitorum, systematizes generating functions and partial-fraction extraction of recurrence solutions.
1759 — Joseph-Louis Lagrange develops the general theory of linear difference and differential equations in parallel, clarifying the role of repeated roots.
1782 — Pierre-Simon Laplace advances the operational/symbolic treatment of difference equations in probability theory (Théorie analytique des probabilités, 1812).
1843 — Jacques Binet publishes the closed-form $\frac{ϕ ^{n} - ψ ^{n}}{5}$ , which thereafter bears his name despite earlier knowledge.
1860s — George Boole, A Treatise on the Calculus of Finite Differences, gives the definitive 19th-century exposition of difference equations, including the operator $E$ and undetermined coefficients.
1939 — Paul Samuelson applies second-order recurrences to macroeconomic business cycles, popularizing the dynamical interpretation of complex roots.
20th c. — The companion-matrix/eigenvalue viewpoint and connections to control theory and numerical stability (Dahlquist's analysis of multistep methods, 1956) place recurrences firmly within linear algebra and dynamical systems.

Subtleties & Limits

The clean closed-form theory is fragile outside the linear-constant-coefficient world.

Variable coefficients. For $a_{n} = p (n) a_{n - 1} + q (n) a_{n - 2}$ with polynomial $p, q$ , no characteristic-polynomial method exists in general. Whether such a recurrence admits a closed-form (hypergeometric or "Liouvillian") solution is decidable by Petkovšek's algorithm (1992) and the Gosper/Zeilberger machinery, but a general elementary solution need not exist.
Nonlinear recurrences. Even the innocent-looking logistic map $a_{n + 1} = λ a_{n} (1 - a_{n})$ has no closed form for general $λ$ and exhibits chaos; superposition fails entirely.
Skolem's Problem. For a linear recurrence over the integers, deciding whether some term equals zero (the Skolem–Mahler–Lech zero set is known to be eventually periodic) is not known to be decidable — a long-standing open problem at the boundary of number theory and computability, despite the apparent simplicity of the underlying recurrence.
Repeated-root forcing combinations. When $f (n)$ is itself a sum of resonant and non-resonant terms, the correct particular ansatz requires treating each piece with its own resonance multiplier; bookkeeping errors here are the most common source of incorrect final answers.