Solve linear recurrences by iteration/expansion

Historical Context & Motivation

Recurrence relations—equations that define each term of a sequence in terms of previous terms—are among the oldest structures in mathematics. Long before the formal language of discrete mathematics existed, mathematicians encountered sequences whose patterns demanded systematic methods for extracting explicit, closed-form expressions. The method of iteration (also called expansion or unrolling) is perhaps the most intuitive of all such techniques: substitute the recurrence into itself repeatedly until a pattern emerges, then collapse the pattern into a formula. Despite its conceptual simplicity, this approach has powered discoveries from Fibonacci's rabbit counting to the analysis of divide-and-conquer algorithms.

The central question this lesson addresses is deceptively simple: given a recurrence relation and an initial condition, how can we repeatedly substitute the defining rule into itself to reveal a summation or product pattern, then express the result as a closed-form formula that depends only on n and the initial value? Mastering this technique builds the intuition that underpins more advanced methods such as the characteristic-root technique and the Master Theorem.

Core Principles & Definitions

Before diving into the mechanics of iteration, it is essential to formalize several foundational ideas. A recurrence relation defines a sequence {a_n} by expressing each term a_n as a function of one or more preceding terms and, possibly, of n itself. When the relation is linear (no products or powers of previous terms) and involves a constant number of predecessors, it is called a linear recurrence with constant coefficients—precisely the class most amenable to the iteration method.

Visual Explanation — Unrolling a Recurrence

The following diagram illustrates the iteration process for a first-order linear recurrence of the form a_n = c · a_n−1 + f(n). Each row represents one substitution step: the recursive term is replaced by its own definition, and the non-homogeneous part f(n) accumulates as a growing sum. The leftmost column tracks the multiplicative coefficient applied to the initial condition a₀, while the right side displays the accumulated summation terms.

Observe how each step introduces one more term in the growing summation and simultaneously increases the exponent on the coefficient c that multiplies the initial condition. The pattern stabilizes after exactly n substitutions, at which point the recurrence has been fully unrolled to the base case. Recognizing this summation pattern—and evaluating it using known series formulas—is the crux of the iteration method.

Mathematical Framework

We now formalize the iteration procedure for first-order linear recurrences. Consider the general first-order linear recurrence with constant coefficient c and a forcing function f(n).

Iteration proceeds by replacing the recursive call on the right-hand side with its own definition. After one substitution we obtain a_n = c(c · a_n−2 + f(n−1)) + f(n) = c² · a_n−2 + c · f(n−1) + f(n). Continuing for k substitutions yields the following intermediate form.

Setting k = n reaches the base case a₀, and we obtain the general closed form.

Common Forms & Classification

Not every recurrence looks identical, so it is helpful to classify the most common first-order forms and the summations they produce upon iteration. The table below catalogues four archetypes: the homogeneous case, the constant-forcing case, the linear-forcing case, and the exponential-forcing case. Each row shows the recurrence, the expanded summation obtained after full iteration, and the resulting closed form.

The flowchart above provides a systematic way to navigate the iteration result. In practice, the critical skill is recognizing the summation produced by the expansion and matching it to a known formula. Most frequently, you will encounter geometric series (when f(n) is constant or exponential) or arithmetic-geometric hybrid sums (when f(n) is polynomial).

Worked Example

Let us solve the recurrence a_n = 3a_n−1 + 2 with initial condition a₀ = 1 using the iteration method.

Strengths, Limitations & Comparisons

The iteration method is one of several techniques available for solving recurrence relations. Understanding its strengths and limitations relative to alternatives helps you choose the right tool for a given problem. Below we compare iteration with the characteristic-root method, generating functions, and the Master Theorem.

Connection to Advanced Theory

The iteration technique does not exist in isolation; it directly connects to several deeper ideas in discrete mathematics and computer science. In algorithm analysis, the recurrences that arise from divide-and-conquer algorithms—such as T(n) = aT(n/b) + f(n)—are routinely solved by a form of iteration called recursion-tree expansion, which is essentially the iteration method applied to a recurrence with a multiplicative argument reduction instead of a subtractive one. The Master Theorem itself was originally motivated by iterating such recurrences and observing recurring patterns in the resulting sums.

Perhaps the most elegant connection is to generating functions. The summation Σ cʲ · f(n−j) produced by iteration is, in fact, a discrete convolution. In the generating-function framework, convolution corresponds to multiplication of two formal power series. This means that the entire iteration procedure—substitution, accumulation, and evaluation—can be compressed into a single algebraic identity in the world of generating functions. Gaining comfort with iteration thus provides the conceptual scaffolding for the more abstract machinery you will encounter in advanced combinatorics courses.

Practice Problems

Summary & Review