Recurrence Relations

A recurrence relation defines a sequence by relating later terms to earlier ones. Instead of saying “the n-th term equals some explicit function of n,” we say “the n-th term is computed from previous terms.”

Why this matters in discrete math and CS:

• •Many counting problems naturally “build” solutions from smaller sizes.
• •Many algorithms (especially dynamic programming and divide-and-conquer) have running times described recursively.
• •Recurrences capture structure: what information from the past is needed to produce the next value.

Sequences: explicit vs recursive

An explicit definition might be:

• •aₙ = 3·2ⁿ (geometric)

A recursive (recurrence) definition might be:

• •a₀ = 3
• •aₙ = 2aₙ₋₁ for n ≥ 1

Both define the same sequence, but the recursive version highlights the “local rule.”

Order and initial conditions

A recurrence can depend on one or more previous terms.

• •Order 1: aₙ depends on aₙ₋₁ only.
• •Order k: aₙ depends on aₙ₋₁, aₙ₋₂, …, aₙ₋ₖ.

To uniquely define a sequence, you need enough starting values (initial conditions):

• •Order 1 needs 1 initial value (like a₀).
• •Order k needs k initial values (like a₀, a₁, …, aₖ₋₁).

Example (order 2):

• •a₀ = 0, a₁ = 1
• •aₙ = aₙ₋₁ + aₙ₋₂

That’s Fibonacci.

The class we’ll solve: linear homogeneous constant-coefficient

This lesson focuses on a very solvable and very common family:

A recurrence is linear if terms appear in a linear combination (no products like aₙ₋₁·aₙ₋₂ and no squares like aₙ₋₁²).

It is homogeneous if there is no “extra” term depending only on n (no added constant or function f(n)).

It has constant coefficients if the weights don’t change with n.

So the standard form is:

aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ⋯ + cₖaₙ₋ₖ

with fixed constants c₁, …, cₖ.

We’ll learn the main trick for solving these: the characteristic equation. The motivation is simple: if the recurrence behaves like repeated multiplication, then exponentials rⁿ are natural building blocks.

To solve

aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ⋯ + cₖaₙ₋ₖ,

we want a closed form for aₙ.

Why guess aₙ = rⁿ?

A key observation: exponentials have the property that shifting the index multiplies by a constant:

• •If aₙ = rⁿ, then aₙ₋₁ = rⁿ⁻¹ = r⁻¹·rⁿ, and generally aₙ₋ⱼ = rⁿ⁻ⱼ = r⁻ⱼ·rⁿ.

That means a linear combination of shifted terms becomes a multiple of rⁿ.

Deriving the characteristic polynomial

Assume a trial solution aₙ = rⁿ (with r ≠ 0). Substitute into the recurrence:

rⁿ = c₁rⁿ⁻¹ + c₂rⁿ⁻² + ⋯ + cₖrⁿ⁻ᵏ

Factor out rⁿ⁻ᵏ (or divide by rⁿ⁻ᵏ) to get a polynomial in r. A clean approach is to divide both sides by rⁿ⁻ᵏ:

rᵏ = c₁rᵏ⁻¹ + c₂rᵏ⁻² + ⋯ + cₖ

Bring everything to one side:

rᵏ − c₁rᵏ⁻¹ − c₂rᵏ⁻² − ⋯ − cₖ = 0

This polynomial

P(r) = rᵏ − c₁rᵏ⁻¹ − c₂rᵏ⁻² − ⋯ − cₖ

is the characteristic polynomial, and the equation P(r) = 0 is the characteristic equation.

Any root r of P(r) = 0 gives a solution aₙ = rⁿ.

Example: Fibonacci characteristic polynomial

Fibonacci recurrence:

aₙ = aₙ₋₁ + aₙ₋₂

Here k = 2, c₁ = 1, c₂ = 1.

Characteristic equation:

r² = r + 1

r² − r − 1 = 0

Roots:

r = (1 ± √5)/2

So we already know rⁿ terms will appear in the closed form.

Why this works (intuition)

The recurrence is a linear transformation that maps a “state” of k previous values to the next one. Exponentials rⁿ behave like eigenvectors of the shift operator: shifting n corresponds to scaling by r. The characteristic equation is essentially the eigenvalue condition.

You don’t need linear algebra to use this method, but it explains why exponentials and polynomials-in-n times exponentials show up.

What we get from roots

• •Distinct roots → sum of exponentials.
• •Repeated roots → exponential times polynomial factors in n.

We’ll make that precise next.

Once you have the characteristic polynomial P(r), solving the recurrence becomes a “root bookkeeping” problem.

Case A: Distinct roots

Suppose P(r) has k distinct roots r₁, r₂, …, rₖ.

Then the general solution is

aₙ = α₁r₁ⁿ + α₂r₂ⁿ + ⋯ + αₖrₖⁿ

where α₁, …, αₖ are constants determined by the initial conditions.

Why we can add solutions:

• •The recurrence is linear and homogeneous.
• •If sequences xₙ and yₙ each satisfy it, then (xₙ + yₙ) also satisfies it.
• •Scaling a solution by a constant also preserves being a solution.

So once we have building blocks rᵢⁿ, linear combinations are still solutions.

Case B: Repeated roots

If r is a root of multiplicity m (meaning (r − r₀)ᵐ divides P(r)), we don’t get m linearly independent solutions by repeating rⁿ.

Instead, the m independent solutions are:

rⁿ, n·rⁿ, n²·rⁿ, …, nᵐ⁻¹·rⁿ

So the contribution of a repeated root r with multiplicity m is:

(β₀ + β₁n + β₂n² + ⋯ + βₘ₋₁nᵐ⁻¹) rⁿ

where βⱼ are constants.

Quick example of a repeated root

Consider

aₙ = 2aₙ₋₁ − aₙ₋₂

Characteristic equation:

r² = 2r − 1

r² − 2r + 1 = 0

(r − 1)² = 0

So r = 1 is a root of multiplicity 2.

General solution:

aₙ = (α + βn)·1ⁿ = α + βn

So the sequence must be linear in n.

Solving for constants using initial conditions

You always use the initial values to solve for α’s (and β’s). This is usually a small linear system.

For distinct roots r₁, …, rₖ:

Given a₀, a₁, …, aₖ₋₁,

set up equations:

a₀ = α₁r₁⁰ + ⋯ + αₖrₖ⁰

a₁ = α₁r₁¹ + ⋯ + αₖrₖ¹

…

aₖ₋₁ = α₁r₁ᵏ⁻¹ + ⋯ + αₖrₖᵏ⁻¹

Solve for αᵢ.

For repeated roots, you do the same but with the polynomial factors.

Reality check: complex roots

Sometimes P(r) has complex roots. That’s not a problem.

If coefficients cᵢ are real, complex roots come in conjugate pairs (a ± bi). Their contributions combine to a real sequence. Often you can rewrite them using cos and sin:

If r = ρe^{iθ}, then rⁿ = ρⁿe^{inθ}

and the real solutions look like:

ρⁿ( A cos(nθ) + B sin(nθ) )

You won’t always need this form, but it’s useful when oscillations appear.

Summary table: root patterns → solution patterns

At this point, you can solve a large fraction of recurrence relations that show up in discrete math courses and CS analysis.

Recurrence relations are not just a math curiosity—they are a core tool for reasoning about programs.

1) Algorithm running times

Many algorithms are defined recursively, so their runtimes are too.

Example: if a function does two recursive calls on size n−1 plus O(1) work, you might get:

T(n) = 2T(n−1) + 1

This one is not homogeneous (there’s a +1), so characteristic polynomials alone don’t finish it—but the homogeneous part still guides the growth. You can often solve the homogeneous part first, then find a particular solution.

Even when you ultimately use the Master Theorem or substitution, having recurrence intuition helps you avoid mistakes.

2) Dynamic programming (DP)

DP problems typically define optimal values by recurrences.

Example shape:

DP[n] = min( DP[n−1] + cost₁, DP[n−2] + cost₂, … )

Those aren’t linear recurrences (because of min/max), but the mindset is the same: compute a sequence from earlier values.

Recurrence relations teach you:

• •what “state” is required (order k)
• •why base cases matter
• •how dependency structure controls complexity

This directly unlocks Dynamic Programming.

3) Closed forms reveal growth rates

Suppose you solve:

aₙ = 3aₙ₋₁ − 2aₙ₋₂

n ≥ 2

Characteristic equation:

r² − 3r + 2 = 0

(r − 1)(r − 2) = 0

Solution:

aₙ = α·1ⁿ + β·2ⁿ = α + β·2ⁿ

As n grows, β·2ⁿ dominates (unless β = 0). This kind of analysis is everywhere in complexity and combinatorics: the largest-magnitude root typically dictates asymptotic behavior.

4) Bridge to generating functions

Characteristic polynomials are one way to solve linear recurrences.

Generating functions are another, often more powerful for:

• •non-homogeneous recurrences
• •combinatorial counting with “add one object” logic

Knowing characteristic roots makes generating-function solutions feel less mysterious: both techniques transform a recurrence into an algebraic object (a polynomial or power series) you can manipulate.

This connects to Generating Functions.

5) Divide-and-conquer

Divide-and-conquer often yields recurrences like:

T(n) = aT(n/b) + f(n)

Those aren’t constant-coefficient in n, so the characteristic polynomial method doesn’t directly apply, but you’ll reuse the same habits:

• •identify the recurrence structure
• •unroll a few steps
• •infer a closed form or tight bound

That prepares you for Divide and Conquer.

Big picture

Characteristic equations give you a “closed form lens.” Even if you later switch to asymptotic methods, you’ll have a mental model of what sequences are capable of doing: exponential growth, oscillation, polynomial factors from repeated roots, and mixtures of these behaviors.