Skip to main content

Recurrences Arise from Structural Decomposition

What This Concept Is​

A recurrence relation describes a quantity in terms of earlier instances of the same quantity: $a_n$ is given as a function of $a_{n-1}, a_{n-2}, \ldots$. In combinatorics, recurrences are not arbitrary equations. They come from breaking objects of size $n$ into smaller structural cases, with each case expressed in terms of counts of smaller size.

The real task is to identify a state that captures exactly enough information for the recursive decomposition to work. Too little state, and the cases overlap or omit possibilities; too much, and the recurrence becomes unnecessarily complex.

Three ingredients are required for every well-posed recurrence:

  1. A precise definition of $a_n$ -- what set of objects is being counted as a function of $n$?
  2. A recursive case split -- how does every object of size $n$ correspond to a unique combination of one or more smaller objects?
  3. Base cases -- explicit values of $a_0, a_1, \ldots$ for enough small $n$ to seed the recurrence.

Skipping any of the three gives you a formula that sometimes agrees with small values -- which is not the same thing as a proof. Pattern-matching from the first few terms is how most wrong recurrences are invented.

Linear vs nonlinear; homogeneous vs nonhomogeneous. Recurrences classify along two axes:

  • linear if $a_n$ depends on earlier $a_i$ only through a linear combination (with coefficients possibly depending on $n$); nonlinear otherwise (Catalan's convolution is nonlinear in the sequence).
  • homogeneous if there is no extra "forcing term" (no $f(n)$ added on the side); nonhomogeneous otherwise.

Linear homogeneous with constant coefficients is the easiest class -- closed form is guaranteed by the characteristic-root method (next concept). Nonlinear recurrences sometimes have closed forms (Catalan) and sometimes do not; generating functions are the universal solver of choice.

Why It Matters Here​

Recurrences connect counting, induction, and algorithms:

  • counting recursively defined objects (binary strings, trees, tilings)
  • analyzing recursive procedures (divide-and-conquer runtime, dynamic programming)
  • proving closed-form formulas by induction, once a recurrence is in hand

Downstream, this concept becomes essential in Semester 2's algorithm analysis, where runtimes themselves satisfy recurrences ($T(n) = 2T(n/2) + n$ for merge sort; $T(n) = T(n-1) + O(n)$ for selection sort). The Master Theorem is a closed-form solver for a restricted class of these. Semester 3's dynamic programming is the engineering practice of recurrence design: finding the smallest state space that supports the decomposition.

Concrete Examples​

Example 1: no two consecutive 1s. Let $a_n$ be the number of binary strings of length $n$ with no two consecutive 1s.

Decompose by the last bit:

  • If the string ends in 0, the first $n-1$ bits form any valid string of length $n-1$: contributes $a_{n-1}$.
  • If the string ends in 1, the bit before it must be 0 (otherwise we would have 11), so the string ends in ...01, and the first $n-2$ bits form any valid string of length $n-2$: contributes $a_{n-2}$.

The cases are disjoint (a string either ends in 0 or 1) and exhaustive. Therefore:

$$a_n = a_{n-1} + a_{n-2}, \qquad a_0 = 1,\ a_1 = 2.$$

Check: $a_0 = 1$ (empty string), $a_1 = 2$ (0 or 1), $a_2 = 3$ (00, 01, 10), $a_3 = 5$. These are Fibonacci numbers, shifted by two -- confirming OEIS A000045 in shifted form.

Example 2: staircase tilings. Let $T_n$ = number of ways to tile a $1 \times n$ strip with tiles of size $1$ and $2$.

Case on the leftmost tile:

  • size-$1$ tile on the left $\to$ the remaining $n-1$ strip has $T_{n-1}$ tilings.
  • size-$2$ tile on the left $\to$ the remaining $n-2$ strip has $T_{n-2}$ tilings.

Therefore $T_n = T_{n-1} + T_{n-2}$, with $T_0 = 1$ (one empty tiling) and $T_1 = 1$ (one single-tile tiling). This is the same recurrence as Example 1 -- which is not coincidence: both are Fibonacci-type and a direct bijection exists between the two sets of objects.

Example 3: Towers of Hanoi. Let $H_n$ = minimum moves to transfer $n$ disks from peg A to peg C using peg B as auxiliary. The recursive strategy is: move the top $n-1$ to B, move disk $n$ to C, move the $n-1$ from B to C. Hence

$$H_n = 2 H_{n-1} + 1, \qquad H_0 = 0.$$

Solving (unrolling or by guessing $H_n = 2^n - 1$ and verifying by induction) gives $H_n = 2^n - 1$. The structural decomposition yields both the recurrence and a proof that the strategy is optimal.

Example 4: Catalan recurrence. Let $C_n$ = number of balanced parenthesizations of $n$ pairs, i.e., strings with $n$ "(" and $n$ ")" such that every prefix has $\ge$ as many "(" as ")". Decompose by the position where the opening "(" at position $1$ closes: if it closes at position $2k + 2$, the substring strictly between forms a balanced string on $k$ pairs, and the substring after forms a balanced string on $n - 1 - k$ pairs. Therefore

$$C_n = \sum_{k=0}^{n-1} C_k, C_{n-1-k}, \qquad C_0 = 1.$$

The small values $1, 1, 2, 5, 14, 42, 132, \ldots$ are the Catalan numbers, which also count BSTs on $n$ keys, Dyck paths, triangulations of an $(n+2)$-gon, stack-sortable permutations, and many other structures (Stanley lists over 100). This recurrence solves to the closed form $C_n = \binom{2n}{n}/(n+1)$, covered in the next concept via generating functions.

Common Confusion / Misconceptions​

  • Insufficient state. If the next step depends on information your state does not carry, the recurrence is wrong. Example: counting binary strings avoiding 010 cannot be done by tracking only length -- you need at least the last one or two bits. The state must encode everything the transition needs.
  • Pattern-matching from small values. Computing $a_0, a_1, \ldots, a_5$ and fitting a formula by inspection is fast but dangerous. Many sequences look linear or quadratic for the first few terms and then diverge. Always verify the formula by an induction argument.
  • Missing a case. Forgetting the edge where the last bit is 1 but the string has length $1$ is a typical omission. Base cases must cover every $n$ below the depth of the recurrence.
  • Initial conditions set wrong. If $a_0$ counts the empty object, it is usually $1$ (one empty string, one empty tree, one empty tiling). Setting $a_0 = 0$ out of habit breaks the formula.
  • Confusing order-$k$ recurrences with ones needing auxiliary sequences. Some problems produce systems of coupled recurrences (e.g., two or three states). Writing a single sequence when two are needed is a modeling error, not a formula error.
  • Arithmetic fluency vs structural fluency. Learners can often solve a given recurrence but cannot derive it from a problem statement. The harder skill is the derivation; practice it until second nature.

How To Use It​

To derive a recurrence:

  1. define the counted object $a_n$ in one sentence of plain English.
  2. choose a parameter -- length, size, number of vertices, total weight.
  3. identify the first or last meaningful structural choice (the boundary decision): last letter, leftmost tile, root's first child, outermost bracket.
  4. split objects by that choice into disjoint exhaustive cases.
  5. express each case's count in terms of $a_m$ for some $m < n$.
  6. write explicit base cases $a_0, a_1, \ldots$ up to the depth of the recurrence.
  7. verify by computing $a_2, a_3, a_4$ two ways: via the recurrence and via direct enumeration; they must agree.

If cases overlap or omit possibilities, the recurrence is wrong even if the first few values look plausible. Trust the model, not the coincidence.

A debugging ritual. Before you move to solving, write out $a_0, a_1, \ldots, a_5$ two ways: by the recurrence you derived, and by direct enumeration of the combinatorial objects. If they disagree anywhere, the recurrence is wrong; if they agree, you have evidence (not proof) that the recurrence is correct, and you can proceed to solving.

Transfer / Where This Shows Up Later​

  • Semester 2 algorithms: runtime recurrences are the bread and butter of algorithm analysis. Merge sort $T(n) = 2T(n/2) + n$; binary search $T(n) = T(n/2) + 1$; selection sort $T(n) = T(n-1) + n-1$. The Master Theorem solves divide-and-conquer forms.
  • Semester 3 data structures: BST/heap amortized analysis uses recurrences in potential-function arguments. Dynamic programming is recurrence design: choose the state, derive the transition, compute bottom-up.
  • Semester 5 OS & 6 distributed systems: queueing-theory analyses (M/M/1, M/D/1) yield recurrences in steady-state probabilities; Markov-chain transient analysis uses $n$-step recurrences.
  • Semester 7 architecture: system-scaling models often fit Amdahl-like recurrences for cumulative latency across service boundaries.
  • Semester 4 databases: result-set size of recursive SQL CTEs satisfies recurrences; termination proofs depend on the recurrence converging.
  • Semester 2 algorithms (specific): quicksort's expected comparisons $T(n) = (n-1) + \tfrac{2}{n}\sum_{k=0}^{n-1} T(k)$; binary-search trees on random keys yield the same recurrence. Solving these produces the $2n\ln n$ expected depth.
  • Machine learning: recurrence-based analyses appear in the convergence rate of iterative optimizers (e.g., $x_{n+1} = (1 - \eta \mu)x_n$ for gradient descent on strongly convex objectives).

Check Yourself​

  1. Why are initial conditions part of the model, not optional add-ons? Give an example where the same recurrence with different $a_0$ produces different sequences.
  2. What makes a case split valid in a recurrence derivation? State both conditions.
  3. Why is pattern-matching from small $n$ strictly weaker than structural decomposition?
  4. For Hanoi, derive $H_n = 2^n - 1$ from $H_n = 2H_{n-1} + 1$ by induction. Why is this a proof of optimality?
  5. Count binary strings of length $n$ containing the substring 11 at least once, using a recurrence. (Hint: complement and reuse Example 1.)
  6. Why does the Catalan recurrence $C_n = \sum_k C_k C_{n-1-k}$ produce convolution rather than simple addition? What does that tell you about the natural solver (next concept)?
  7. For a recurrence $a_n = 2 a_{n-1} + f(n)$ with a nonhomogeneous term $f$, outline how you would solve it. Which part needs a particular solution?

Mini Drill or Application​

Derive recurrences and state the base cases explicitly. Verify each at $n = 3$ by direct enumeration.

  1. Ternary strings of length $n$ with no two adjacent equal symbols.
  2. Ways to climb $n$ stairs using steps of size $1$ or $2$.
  3. Tilings of a $1 \times n$ board using tiles of lengths $1$ and $3$.
  4. Number of $n$-bit binary strings that do not contain 010.
  5. The Catalan numbers $C_n$, counting valid strings of $n$ pairs of balanced parentheses. (Hint: case on the position of the match to the first (, giving $C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}$.)

Read This Only If Stuck​