Formulate recurrence relations from problems - Discrete Math

SECTION 1

Historical Context & Motivation

Long before the language of modern discrete mathematics was codified, mathematicians recognized that many natural sequences obey a simple principle: each term can be expressed as a function of the terms that precede it. This observation — that the present is determined by the past — is the philosophical kernel of a recurrence relation. The history of formulating such relations intertwines with the development of combinatorics, number theory, and algorithm analysis, reflecting a persistent human desire to compress infinite sequences into finite rules.

1202 • Fibonacci's Liber Abaci

Leonardo of Pisa posed his famous rabbit-breeding problem, yielding the recurrence F(n) = F(n−1) + F(n−2). This is arguably the earliest well-known instance of translating a word problem into a recurrence relation.

1718 • de Moivre & Generating Functions

Abraham de Moivre introduced the technique of solving linear recurrences via characteristic equations and generating functions, providing a systematic framework for closed-form solutions.

1821 • Cauchy's Formal Analysis

Augustin-Louis Cauchy formalized the theory of difference equations in his Cours d'Analyse, establishing rigorous foundations for both continuous and discrete recursive structures.

1960s • Algorithm Analysis Era

With the rise of computer science, Donald Knuth and others popularized the use of recurrence relations to analyze the running time of recursive algorithms such as merge sort, binary search, and quicksort.

1990s–Present • Modern Combinatorics & CS

Recurrence formulation is now a standard tool across dynamic programming, computational biology (sequence alignment), financial modeling, and combinatorial enumeration.

The central challenge has remained constant across centuries: given a problem described in natural language — whether it concerns breeding rabbits, climbing staircases, or partitioning data — how does one systematically identify the recursive structure and express it as a precise mathematical relation? Mastering this translation step is the gateway to solving the recurrence, whether by iteration, characteristic roots, generating functions, or the Master Theorem.

SECTION 2

Core Principles & Definitions

Before diving into formulation techniques, it is essential to establish precise definitions and the guiding principles that underpin recurrence relations. A recurrence relation for a sequence {a_n} is an equation that expresses a_n as a function of one or more preceding terms a_n−1, a_n−2, …, together with initial conditions that anchor the sequence at its starting values. The order of a recurrence is the difference between the largest and smallest indices appearing in it — a second-order recurrence, for example, relates a_n to a_n−1 and a_n−2.

Identify the Sequence

Define what you are counting or measuring. Assign a name — typically a_n or T(n) — and state the parameter n explicitly (e.g., number of steps, size of input).

Think One Step Back

Ask: what choices or events lead to a state of size n? Decompose the problem at stage n into subproblems of smaller size. This decomposition is the heart of the recurrence.

Combine Subproblems

Determine how the subproblem solutions combine — by addition (disjoint cases), multiplication (independent choices), or a more complex function — to produce a_n.

Set Initial Conditions

Identify the smallest non-trivial cases and compute their values directly. A k-th order recurrence requires exactly k initial conditions to determine the sequence uniquely.

Verify by Computing

Use the recurrence plus initial conditions to generate the first several terms. Cross-check these against direct enumeration or known results to confirm correctness.

✦

KEY TAKEAWAY

Formulating a recurrence is like writing assembly instructions for flat-pack furniture: you describe how to build the size-n structure by assuming you already have the size-(n−1) structure in hand. The initial conditions are the first few pieces you assemble by hand before the pattern kicks in. If you can articulate 'I build the big thing from smaller copies of the same thing, plus some extra work,' you have a recurrence.

SECTION 3

Visual Explanation — The Staircase Problem

One of the most intuitive illustrations of recurrence formulation is the classic staircase-climbing problem: a person can climb 1 or 2 steps at a time — in how many distinct ways can they reach the n-th step? The diagram below visualizes the recursive decomposition for n = 5, showing how every path to step n either arrives from step n−1 (via a single step) or from step n−2 (via a double step). This mutual exclusivity means the total number of ways satisfies S(n) = S(n−1) + S(n−2), with initial conditions S(1) = 1 and S(2) = 2.

The staircase for n = 5 steps. Every path to Step 5 must pass through either Step 4 (solid pink arrow, +1 move) or Step 3 (dashed amber arrow, +2 move). Since these cases are mutually exclusive, S(5) = S(4) + S(3) = 5 + 3 = 8.

Notice how the visual decomposition encapsulates the entire formulation strategy. We did not attempt to enumerate all 8 paths; instead, we asked: what was the last action taken? This last-step analysis is the single most powerful heuristic for constructing recurrences from combinatorial problems. By partitioning the set of all valid configurations according to the final decision, we guarantee that the subsets are exhaustive and mutually exclusive, which justifies adding the sub-counts.

SECTION 4

Mathematical Framework

The formulation of recurrence relations draws on several standard mathematical templates. Recognizing which template applies to a given problem dramatically accelerates the modeling process. Below we catalog the most common forms encountered in discrete mathematics and computer science, along with the variable definitions and contexts in which they arise.

FIRST-ORDER LINEAR RECURRENCE

a(n) = c · a(n − 1) + f(n), n ≥ 1

Here c is a constant multiplier (the homogeneous coefficient), and f(n) is a forcing function that may depend on n. When f(n) = 0 the recurrence is homogeneous. Example: compound interest, where the balance at year n equals (1 + r) times the balance at year n−1 plus a deposit d.

SECOND-ORDER LINEAR RECURRENCE

a(n) = p · a(n − 1) + q · a(n − 2), n ≥ 2

Two preceding terms contribute to a(n). The Fibonacci sequence (p = q = 1) and the Lucas numbers are canonical examples. Solving involves the characteristic equation x² − px − q = 0.

DIVIDE-AND-CONQUER RECURRENCE

T(n) = a · T(n / b) + f(n), n > 1

This models algorithms that split input of size n into a subproblems of size n/b, with f(n) representing the cost of dividing and combining. Merge sort corresponds to a = 2, b = 2, f(n) = Θ(n). Analyzed via the Master Theorem.

FULL HISTORY / SUMMATION RECURRENCE

a(n) = Σ (from k = 0 to n − 1) g(k) · a(k) + h(n)

When a(n) depends on all previous terms — not just a fixed number of predecessors — we have a full-history recurrence. Quicksort's average-case analysis produces such a relation. These are often converted to simpler forms by algebraic manipulation (e.g., subtracting the (n−1)-th equation from the n-th).

💡

Formulation Heuristic

When confronted with a new problem, begin by asking three questions: (1) What quantity does a(n) represent? (2) What are the possible last actions or first decisions that partition the problem into smaller instances? (3) Are the resulting subproblems of the same type as the original? If yes, you have a recurrence.

SECTION 5

Formulation Strategies & Classification

Different problem domains call for different decomposition strategies. The table below classifies the most common approaches and pairs each with a representative problem. After the table, a second diagram illustrates the decision-tree decomposition strategy, which is particularly useful for problems involving constrained sequences (e.g., binary strings without consecutive 1s).

Strategy	Key Question	Example Problem
Last-Step Analysis	What was the final action that produced a configuration of size n?	Tiling a 2 × n board with dominoes; staircase climbing
First-Element Classification	How does the first element constrain the remaining elements?	Binary strings of length n with no two consecutive 1s
Divide and Conquer	Can the input be split into equal (or near-equal) parts that are solved independently?	Merge sort time complexity; Karatsuba multiplication
Inclusion of a Distinguished Element	Does a particular element participate in the structure or not?	Number of subsets of size k from {1, …, n}; Bell numbers
State-Based (Multi-Sequence)	Are there multiple 'types' of valid configurations, each leading to a separate recurrence?	Strings over {a, b, c} ending in 'a' vs. not ending in 'a'

Common recurrence-formulation strategies

The first-element classification applied to binary strings with no consecutive 1s. Starting with 0 leaves a free subproblem of size n−1. Starting with 1 forces the next bit to be 0, leaving a subproblem of size n−2. The recurrence a(n) = a(n−1) + a(n−2) is precisely the Fibonacci pattern with shifted initial conditions.

The diagram reveals an important observation: the constraint (no consecutive 1s) is what forces the second branch to consume two positions rather than one, elevating the recurrence from first order to second order. In general, constraints that propagate across multiple positions increase the order of the recurrence and may require a state-based (multi-sequence) formulation when the propagation is more complex.

SECTION 6

Worked Example — Tower of Hanoi

The Tower of Hanoi asks: given n disks of decreasing size stacked on one peg, move all of them to a target peg, one disk at a time, never placing a larger disk on a smaller one. Let T(n) denote the minimum number of moves required. We will formulate the recurrence from scratch.

Formulating the Tower of Hanoi Recurrence

1
Step 1 — Define the Sequence

Let T(n) = the minimum number of moves to transfer n disks from peg A to peg C, using peg B as auxiliary. The parameter n is the number of disks.
2
Step 2 — Think One Step Back (Decompose)

To move the bottom (largest) disk from A to C, the n−1 disks above it must first be moved out of the way — to peg B. This sub-task is exactly the Tower of Hanoi problem with n−1 disks, requiring T(n−1) moves. Then we move the largest disk from A to C (1 move). Finally, we move the n−1 disks from B to C, again requiring T(n−1) moves.
3
Step 3 — Combine Subproblems

The three phases are sequential, so we sum: T(n) = T(n−1) + 1 + T(n−1) = 2·T(n−1) + 1.

T(n) = 2·T(n − 1) + 1
4
Step 4 — Set Initial Condition

With a single disk (n = 1), we simply move it directly from A to C.

T(1) = 1
5
Step 5 — Verify by Computing

T(1) = 1. T(2) = 2·1 + 1 = 3. T(3) = 2·3 + 1 = 7. T(4) = 2·7 + 1 = 15. Checking against known solutions confirms correctness. The closed form T(n) = 2ⁿ − 1 can be derived from this first-order linear recurrence.

Sequence: 1, 3, 7, 15, 31, … = 2ⁿ − 1 ✓

ℹ

Why This Works

The key insight is that moving the largest disk requires a clear destination and a clear source, which means all other disks must be on the auxiliary peg. This forces the problem to split into two identical subproblems of size n−1, each of the same type as the original — the hallmark of a valid recursive decomposition.

SECTION 7

Strengths, Limitations, and Common Pitfalls

Recurrence relations are remarkably versatile modeling tools, but formulating them correctly requires awareness of subtle pitfalls. The table below summarizes the main strengths and limitations of the recurrence-formulation approach, and the discussion that follows highlights the errors most frequently encountered by students.

Strengths	Limitations
Converts complex combinatorial reasoning into compact algebraic equations	Choosing the wrong decomposition variable can yield an intractable or incorrect relation
Natural fit for problems with recursive structure (trees, divide-and-conquer algorithms, nested decisions)	Overlapping subproblems may be missed, leading to over-counting if cases are not truly disjoint
Systematic solution methods exist (characteristic roots, generating functions, Master Theorem)	Non-linear recurrences or those with variable coefficients may lack closed-form solutions
Enables efficient computation via dynamic programming once formulated	Forgetting or mis-specifying initial conditions renders the recurrence unsolvable or yields a wrong sequence

Strengths vs. limitations of recurrence formulation

⚠

COMMON PITFALLS TO AVOID

Three errors dominate student work. First, non-exhaustive decomposition: failing to account for all possible last actions understates a(n). Second, non-disjoint cases: if two branches of the decomposition overlap, configurations are double-counted. Third, incorrect initial conditions: a correct recurrence with wrong base cases generates the wrong sequence — always verify the first 3–4 values by hand.

SECTION 8

Connection to Advanced Theory

Formulating recurrence relations is not an end in itself — it is the crucial first step that unlocks a rich ecosystem of solution techniques and deeper mathematical structures. Once a recurrence is correctly stated, one can pursue closed-form solutions, asymptotic analysis, or algorithmic implementation via dynamic programming. The table below maps the formulation step to its downstream applications.

After Formulation…	Advanced Technique	Typical Context
Linear constant-coefficient recurrence	Characteristic root method; partial fractions	Fibonacci-type sequences, error-correcting codes
Divide-and-conquer recurrence	Master Theorem; Akra–Bazzi method	Algorithm time-complexity analysis
Combinatorial recurrence	Generating functions (ordinary & exponential)	Counting partitions, Catalan structures, labeled trees
Any recurrence	Dynamic programming (memoization / tabulation)	Optimization problems (knapsack, shortest path, edit distance)

From formulation to solution and application

It is worth emphasizing that the formulation skill transfers seamlessly into dynamic programming, which is essentially the algorithmic realization of a recurrence relation augmented with memoization to avoid redundant computation. Every DP solution begins with a recurrence relation (the Bellman equation in optimization contexts), making the formulation step the intellectual bottleneck of DP problem-solving. Students who master formulation in discrete mathematics thus gain a significant advantage when studying algorithms, operations research, and computational biology.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain in your own words why a recurrence relation for a combinatorial counting problem requires initial conditions. What goes wrong if they are omitted?

Show answer

A recurrence relation defines a(n) in terms of preceding values, but it cannot generate any values without a starting point — the recursion would regress infinitely. Initial conditions anchor the sequence by specifying the values at the smallest non-trivial cases (e.g., a(0) or a(1)). Without them, the recurrence admits infinitely many solutions; for instance, a(n) = 2·a(n−1) is satisfied by a(n) = C·2ⁿ for any constant C. Initial conditions pin down the unique solution relevant to the problem.

Question 2: BASIC CALCULATION

A person climbs a staircase of n steps, taking 1, 2, or 3 steps at a time. Let a(n) be the number of distinct ways to reach step n. Formulate the recurrence relation and state the initial conditions.

Show answer

Using last-step analysis, the person's final move is either 1 step (from step n−1), 2 steps (from step n−2), or 3 steps (from step n−3). These cases are mutually exclusive and exhaustive, giving a(n) = a(n−1) + a(n−2) + a(n−3) for n ≥ 4. The initial conditions are a(1) = 1, a(2) = 2, a(3) = 4. Verification: a(4) = 4 + 2 + 1 = 7, which can be confirmed by direct enumeration of the 7 paths to step 4.

Question 3: INTERMEDIATE

Let b(n) be the number of ternary strings of length n (over {0, 1, 2}) that do not contain the substring '00'. Formulate a recurrence for b(n) and determine b(1) through b(4).

Show answer

Classify strings by their first character. If the first character is 1 or 2 (two choices), the remaining n−1 characters form any valid string → 2·b(n−1). If the first character is 0, the second character must be 1 or 2 (to avoid '00'), and the remaining n−2 characters are any valid string → 2·b(n−2). Thus b(n) = 2·b(n−1) + 2·b(n−2) for n ≥ 3, with b(1) = 3 and b(2) = 8 (all 9 ternary strings of length 2 minus '00'). Verification: b(3) = 2·8 + 2·3 = 22; b(4) = 2·22 + 2·8 = 60.

Question 4: APPLIED

An algorithm processes a list of n items as follows: it examines the first item (constant time), then recursively processes the remaining n−1 items, and finally performs a linear scan of all n items to merge results. Let T(n) be the running time. Formulate the recurrence and identify its closed-form solution.

Show answer

The algorithm spends O(1) on the first item, T(n−1) on the recursive call, and O(n) on the merge scan. This gives T(n) = T(n−1) + c·n + d for constants c, d, with T(1) = e (some constant). Unrolling: T(n) = T(1) + Σ(k=2 to n)[c·k + d] = e + c·[n(n+1)/2 − 1] + d·(n−1). This simplifies to T(n) = O(n²). The recurrence is a first-order linear recurrence with a linearly growing forcing function, and the quadratic closed form reflects the accumulation of linearly growing work at each recursive level.

Question 5: CRITICAL THINKING

Consider the number of ways to tile a 3 × 2n rectangle using 1 × 2 dominoes. Let f(n) denote this count. Argue why a single-sequence recurrence of the form f(n) = α·f(n−1) + β·f(n−2) may not suffice, and propose a multi-sequence (state-based) approach to formulate a valid recurrence system.

Show answer

When tiling a 3 × 2n board column by column, removing the last two columns does not always leave a clean 3 × 2(n−1) sub-board; horizontal dominoes may protrude into the boundary, creating partial column states. A single-sequence recurrence fails because the subproblem is not always of the same type. The solution is to define multiple sequences based on boundary states: let f(n) be the number of tilings of a full 3 × 2n board and g(n) be the number of tilings of the same board with one protruding cell. Then one derives a coupled system: f(n) = f(n−1) + 2·g(n−1) and g(n) = f(n−1) + g(n−1), with f(1) = 3 and g(1) = 1. This multi-sequence approach is the standard technique when the recursive structure introduces heterogeneous sub-configurations. The solution yields f(n) = [((2+√3)^n + (2−√3)^n + 2·

(−1)^n

)] / 4, though deriving this requires solving the coupled system via eigenvalues.

SUMMARY

Lesson Summary

Summary

Formulating a recurrence relation means translating a problem's recursive structure into a precise equation. The process begins by clearly defining the sequence — what a(n) counts or measures — and then performing a decomposition that reduces the size-n problem to subproblems of the same type. The two most powerful decomposition heuristics are last-step analysis (what was the final action?) and first-element classification (how does the first element constrain the rest?). Every correct formulation requires initial conditions to anchor the recursion, and verification against small cases is essential to catch errors in decomposition or base values.

Key recurrence templates include first-order linear (a(n) = c·a(n−1) + f(n)), second-order linear (Fibonacci-type), and divide-and-conquer (T(n) = a·T(n/b) + f(n)). When constraints create heterogeneous subproblem shapes, a state-based multi-sequence approach is required. Mastering the formulation step is the intellectual foundation for solving recurrences via characteristic roots, generating functions, or the Master Theorem, and it is the prerequisite for designing efficient dynamic programming algorithms.