Solve linear recurrences with characteristic equations...

SECTION 1

Historical Context & Motivation

Recurrence relations have appeared throughout mathematics for centuries, long before they were formalized. The most famous example is the Fibonacci sequence, introduced to European mathematics in 1202, where each term is the sum of the two preceding terms. While computing individual terms by hand is straightforward, mathematicians quickly recognized a deeper question: is there a direct formula that yields the n-th term without iterating through every predecessor? The quest for such closed-form solutions drove the development of the characteristic equation method, one of the most powerful techniques in combinatorics and discrete mathematics.

1202

Fibonacci's Liber Abaci

Leonardo of Pisa introduces the rabbit-breeding problem, giving rise to the sequence F(n) = F(n−1) + F(n−2). The recurrence is stated informally without any notion of a general solution technique.

1718

De Moivre's Formula

Abraham de Moivre discovers that assuming a solution of the form rⁿ for a linear recurrence yields an algebraic equation whose roots determine the general solution. This is the birth of the characteristic equation method.

1730

Euler's Systematic Treatment

Leonhard Euler formalizes the connection between linear recurrences and linear differential equations, showing that both share the same algebraic structure of characteristic roots.

1843

Binet's Closed Form for Fibonacci

Jacques Philippe Marie Binet publishes the explicit formula F(n) = (φⁿ − ψⁿ)/√5, demonstrating the power of characteristic roots. The result had been known to Euler and Daniel Bernoulli earlier, but Binet's name became attached to it.

1900s+

Modern Applications

The characteristic equation method becomes indispensable in algorithm analysis, coding theory, signal processing, and combinatorial enumeration, forming a cornerstone of undergraduate discrete mathematics.

The central question that motivated these developments remains the same today: given a linear homogeneous recurrence relation with constant coefficients, how can we bypass iterative computation and jump directly to the value of any term in the sequence? The characteristic equation method provides an elegant and systematic answer.

SECTION 2

Core Principles & Definitions

Before applying the characteristic equation method, we must precisely define the class of recurrences it addresses. A linear recurrence relation with constant coefficients expresses each term of a sequence as a fixed linear combination of a finite number of preceding terms. The word "linear" means that the terms appear only to the first power and are not multiplied together, while "constant coefficients" means the multipliers do not depend on n. When there is no additional non-homogeneous forcing term (like an added function of n), the recurrence is called homogeneous.

Linear Homogeneous Recurrence

A recurrence of the form a(n) = c₁a(n−1) + c₂a(n−2) + ⋯ + cₖa(n−k), where c₁, …, cₖ are constants and cₖ ≠ 0. The order (or degree) of the recurrence is k.

Characteristic Equation

The polynomial equation rᵏ − c₁rᵏ⁻¹ − c₂rᵏ⁻² − ⋯ − cₖ = 0, obtained by substituting the trial solution a(n) = rⁿ into the recurrence. Its roots are called characteristic roots.

Distinct Roots → General Solution

When all k roots r₁, r₂, …, rₖ are distinct, the general solution is a(n) = A₁r₁ⁿ + A₂r₂ⁿ + ⋯ + Aₖrₖⁿ. The constants A₁, …, Aₖ are determined by initial conditions.

Initial Conditions

A k-th order recurrence requires exactly k initial values—a(0), a(1), …, a(k−1)—to uniquely determine the sequence. These values pin down the arbitrary constants in the general solution.

Superposition Principle

Any linear combination of solutions to a linear homogeneous recurrence is itself a solution. This principle justifies building the general solution as a sum of the individual rⁿ solutions.

✦ KEY TAKEAWAY

Think of a recurrence relation as a recipe that tells you how to cook each dish from the previous ones. The characteristic equation method is like reverse-engineering the recipe into a single master formula—an algebraic shortcut that lets you predict any dish number without preparing every one before it. The trial solution a(n) = rⁿ acts as a probe: you plug it in, and the recurrence itself tells you which values of r actually work.

SECTION 3

Visual Explanation: From Recurrence to Closed Form

The flowchart above summarizes the five-step workflow of the characteristic equation method for a second-order recurrence. Starting from the recurrence itself (top left, violet border), we substitute the trial solution rⁿ (cyan), simplify to obtain the characteristic polynomial (pink), solve for its roots (amber), and then branch depending on whether the roots are distinct (emerald) or repeated (orange). In both cases, initial conditions (blue) pin down the constants to produce a unique closed-form expression.

The diagram highlights the core insight of the method: a recurrence is a discrete-time analogue of a differential equation, and just as one guesses exponential solutions for constant-coefficient ODEs, one guesses geometric solutions rⁿ for constant-coefficient recurrences. The algebraic constraint that rⁿ must satisfy the recurrence collapses into a polynomial equation, whose roots completely characterize the solution space. This is why the polynomial is called the characteristic equation: its roots characterize every solution of the recurrence.

SECTION 4

Mathematical Framework

We now develop the method rigorously for a second-order linear homogeneous recurrence with constant coefficients—the most common case encountered in practice. The technique generalizes naturally to higher orders, but the second-order case captures every essential idea.

GENERAL SECOND-ORDER RECURRENCE

a(n) = c₁ · a(n − 1) + c₂ · a(n − 2), n ≥ 2

Here c₁ and c₂ are real constants with c₂ ≠ 0, and the sequence is determined once a(0) and a(1) are specified.

The key ansatz is to try a solution of the form a(n) = rⁿ for some nonzero constant r. Substituting into the recurrence gives rⁿ = c₁rⁿ⁻¹ + c₂rⁿ⁻². Because rⁿ⁻² ≠ 0 for r ≠ 0, we divide both sides by rⁿ⁻² to obtain the characteristic equation.

CHARACTERISTIC EQUATION

r² − c₁ · r − c₂ = 0

This quadratic has two roots (counting multiplicity) by the fundamental theorem of algebra. These roots r₁ and r₂ are called the characteristic roots.

CASE 1 — DISTINCT ROOTS

a(n) = A₁ · r₁ⁿ + A₂ · r₂ⁿ

When r₁ ≠ r₂, the general solution is a linear combination of two linearly independent solutions. The constants A₁ and A₂ are determined by the initial conditions a(0) and a(1).

CASE 2 — REPEATED ROOT

a(n) = (A₁ + A₂ · n) · rⁿ

When r₁ = r₂ = r (a double root), the single exponential rⁿ provides only one linearly independent solution. The second independent solution is n · rⁿ. This mirrors the repeated-root phenomenon in second-order ODEs.

💡 Why n · rⁿ in the Repeated-Root Case?

If r is a double root, then r² − c₁r − c₂ = (r − r₀)² for some r₀, so both the polynomial and its derivative vanish at r₀. A direct verification shows that n · r₀ⁿ satisfies the original recurrence, giving the needed second linearly independent solution. This is entirely analogous to the reduction-of-order technique in differential equations.

SECTION 5

Classifying Recurrences & Identifying the Method

Not every recurrence can be solved by the characteristic equation technique. Before reaching for this tool, you must verify that the recurrence is linear, homogeneous, and has constant coefficients. The following table helps classify common recurrence types and indicates whether the characteristic equation method applies directly.

Classification of recurrences and applicability of the characteristic equation method

Recurrence Example	Linear?	Homogeneous?	Constant Coeff?	Method Applies?
`a(n) = 3a(n−1) − 2a(n−2)`	Yes	Yes	Yes	✓ Yes
`a(n) = 2a(n−1) + 3ⁿ`	Yes	No	Yes	Not directly (need particular solution)
`a(n) = n · a(n−1)`	Yes	Yes	No (coeff = n)	No
`a(n) = a(n−1)²`	No	—	—	No
`a(n) = 5a(n−1) − 6a(n−2)`	Yes	Yes	Yes	✓ Yes

This decision tree shows how to determine whether a given recurrence is amenable to the characteristic equation method. Follow the three yes/no questions: Is it linear? Are the coefficients constant? Is it homogeneous? Only when all three answers are yes does the standard characteristic equation approach apply directly.

SECTION 6

Worked Example: Solving a Second-Order Recurrence

Consider the recurrence relation a(n) = 5a(n − 1) − 6a(n − 2) with initial conditions a(0) = 1 and a(1) = 4. We will apply the characteristic equation method to find a closed-form expression for a(n).

Finding a(n) for a(n) = 5a(n−1) − 6a(n−2), a(0) = 1, a(1) = 4

Step 1 — Write the Characteristic EquationWe substitute a(n) = rⁿ into the recurrence. This gives rⁿ = 5rⁿ⁻¹ − 6rⁿ⁻². Dividing both sides by rⁿ⁻² (valid since r ≠ 0) yields the characteristic equation:

r² − 5r + 6 = 0

Step 2 — Solve the Characteristic EquationFactor the quadratic: r² − 5r + 6 = (r − 2)(r − 3) = 0. The two roots are r₁ = 2 and r₂ = 3. Since the roots are distinct, we use Case 1.

r₁ = 2, r₂ = 3 (distinct roots)

Step 3 — Write the General SolutionWith distinct roots, the general solution is a(n) = A₁ · 2ⁿ + A₂ · 3ⁿ, where A₁ and A₂ are constants to be determined.

a(n) = A₁ · 2ⁿ + A₂ · 3ⁿ

Step 4 — Apply Initial ConditionsSubstitute n = 0: a(0) = A₁ · 2⁰ + A₂ · 3⁰ = A₁ + A₂ = 1. Substitute n = 1: a(1) = A₁ · 2¹ + A₂ · 3¹ = 2A₁ + 3A₂ = 4. This is a system of two linear equations in two unknowns.

System: A₁ + A₂ = 1 and 2A₁ + 3A₂ = 4

Step 5 — Solve the SystemFrom the first equation, A₁ = 1 − A₂. Substituting into the second: 2(1 − A₂) + 3A₂ = 4, which simplifies to 2 + A₂ = 4, giving A₂ = 2. Then A₁ = 1 − 2 = −1.

A₁ = −1, A₂ = 2

Step 6 — State the Closed-Form SolutionSubstituting the constants back into the general solution yields the final answer. We can verify: a(0) = −1(1) + 2(1) = 1 ✓, a(1) = −1(2) + 2(3) = 4 ✓, a(2) = −1(4) + 2(9) = 14, and indeed 5(4) − 6(1) = 14 ✓.

a(n) = −2ⁿ + 2 · 3ⁿ = 2 · 3ⁿ − 2ⁿ

✅ Verification Tip

Always verify your closed-form solution by checking that it satisfies both the recurrence and the initial conditions. Computing a(2) and a(3) from the closed form and from the recurrence provides strong evidence of correctness. In exams, this two-minute check can catch sign errors and save significant points.

SECTION 7

Strengths, Limitations, and Comparisons

The characteristic equation method is remarkably efficient for the class of problems it targets, but it is not a universal tool. Understanding its strengths and limitations helps you choose the right technique for any given recurrence.

Strengths and limitations of the characteristic equation method

Aspect	Strength	Limitation
Speed	Produces a closed form in O(1) computation per term, versus O(n) for iterative unrolling.	Requires solving a polynomial, which may be difficult for order > 2.
Generality	Works for any order k with constant coefficients and homogeneous form.	Does not directly apply to non-constant coefficients, nonlinear, or non-homogeneous recurrences.
Insight	Reveals asymptotic growth rate: the dominant root controls long-term behavior.	Complex roots produce real solutions via trigonometric identities, which can obscure intuition initially.
Exactness	Gives an exact closed form—no approximation involved.	Irrational roots (e.g., Fibonacci's golden ratio) may require careful handling in integer contexts.

✦ KEY TAKEAWAY

The characteristic equation method is to recurrence relations what the Laplace transform is to differential equations: a systematic algebraic technique that converts a recursive (or differential) problem into a purely algebraic one. Once you solve the polynomial, the rest is linear algebra. Keep in mind that the method has well-defined boundaries—non-homogeneous and variable-coefficient recurrences require extensions like the method of undetermined coefficients or generating functions.

SECTION 8

Connection to Advanced Theory

The introductory characteristic equation method covers the case of distinct real roots in a second-order recurrence. In practice, several extensions arise naturally as you encounter more complex problems. The table below previews these extensions and situates the introductory method within the broader landscape.

Introductory vs. advanced characteristic equation techniques

Feature	Introductory Method (This Lesson)	Advanced Extensions
Order	Second-order (k = 2)	Arbitrary order k; characteristic polynomial of degree k
Root types	Distinct real roots, repeated real root	Complex conjugate roots → oscillatory terms via r = R(cos θ + i sin θ)
Homogeneity	Homogeneous only	Non-homogeneous: add a particular solution via undetermined coefficients or variation of parameters
Multiplicity	Double root handled with n · rⁿ	Root of multiplicity m: solutions rⁿ, nrⁿ, n²rⁿ, …, nᵐ⁻¹rⁿ
Alternative tools	Characteristic equation only	Generating functions, matrix exponentiation, Z-transforms

One of the most elegant connections is to matrix exponentiation. Any k-th order linear recurrence can be rewritten as a first-order matrix recurrence v(n) = M · v(n − 1), where M is the companion matrix. The characteristic equation of the recurrence is precisely the characteristic polynomial of M, bridging discrete math, linear algebra, and even computational complexity (since Mⁿ can be computed in O(k³ log n) time via repeated squaring). These connections underscore why mastering the introductory case is so valuable: it lays the algebraic foundation for every subsequent generalization.

SECTION 9

Practice Problems

PROBLEM 1 — CONCEPTUAL

Explain why we substitute a(n) = rⁿ (a geometric/exponential trial solution) into a linear homogeneous recurrence with constant coefficients, rather than, say, a(n) = n² or a(n) = log n. What property of the exponential function makes it a natural choice?

PROBLEM 2 — BASIC CALCULATION

Solve the recurrence a(n) = 7a(n − 1) − 10a(n − 2) with initial conditions a(0) = 2 and a(1) = 1.

PROBLEM 3 — INTERMEDIATE

Solve the recurrence a(n) = 6a(n − 1) − 9a(n − 2) with initial conditions a(0) = 1 and a(1) = 6. Note that this recurrence has a repeated characteristic root.

PROBLEM 4 — APPLIED

A computer scientist analyzes a divide-and-conquer algorithm whose time complexity satisfies T(n) = 3T(n − 1) − 2T(n − 2), with T(0) = 1 (base case cost) and T(1) = 5. Find a closed-form expression for T(n) and determine the asymptotic growth rate of the algorithm.

PROBLEM 5 — CRITICAL THINKING

Prove that if r₁ and r₂ are distinct roots of the characteristic equation r² − c₁r − c₂ = 0, then the sequences {r₁ⁿ} and {r₂ⁿ} are linearly independent (i.e., if A₁r₁ⁿ + A₂r₂ⁿ = 0 for all n ≥ 0, then A₁ = A₂ = 0). Why does this guarantee that the general solution a(n) = A₁r₁ⁿ + A₂r₂ⁿ can satisfy any pair of initial conditions?

SUMMARY

Lesson Summary

The characteristic equation method transforms a linear homogeneous recurrence with constant coefficients into an algebraic problem. By substituting the trial solution a(n) = rⁿ, the recurrence collapses into a polynomial—the characteristic equation—whose roots dictate the form of the general solution. For a second-order recurrence a(n) = c₁a(n − 1) + c₂a(n − 2), the characteristic equation is r² − c₁r − c₂ = 0.

When the roots r₁ and r₂ are distinct, the general solution is a(n) = A₁r₁ⁿ + A₂r₂ⁿ. When there is a repeated root r, the general solution becomes a(n) = (A₁ + A₂n)rⁿ. In both cases, the constants A₁ and A₂ are pinned down by the initial conditions through a system of linear equations. This method, rooted in the work of de Moivre and Euler, remains indispensable in combinatorics, algorithm analysis, and any domain where sequences defined by recurrence relations arise.