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 can encode them but do not guarantee a convenient closed-form solution.

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 after the size shift $a_n=T_{n+1}$, not at equal indices.

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 strategy gives an upper bound. For optimality, before the first move of the largest disk all smaller disks must form a tower on the third peg, requiring at least H(n−1) moves; after its last move to the target they require at least H(n−1) further moves. At least one largest-disk move separates these phases, giving the matching lower bound 2H(n−1)+1.

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)$, an optional deeper result; deriving its coefficient formula requires additional work beyond merely writing the generating-function equation.

Common Confusion / Misconceptions​

  • Insufficient state. If the next step depends on information your state does not carry, the recurrence is wrong. Example: for a direct one-symbol extension process avoiding 010, tracking only the current total count hides relevant suffix information; auxiliary suffix states make the transition correct, though one may subsequently eliminate them to obtain a scalar recurrence. 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 to the workshop model​

Use this concept to justify or challenge one result in the workshop project. Specify the counted objects or graph semantics before interpreting any numerical output.

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​

Use the bounded reading guide to locate the topic in MCS or Rosen. These links open indexes. Check the actual heading in your edition, read one targeted explanation, then reconstruct the argument with the book closed.

The state, initial values and a genuine bijection​

No-adjacent-one words of length n have counts a₀=1,a₁=2; tilings of length n by one- and two-tiles have T₀=T₁=1. Equal recurrence equations therefore do not imply aₙ=Tₙ. Instead aₙ=Tₙ₊₁. Appending zero to a valid word and parsing tokens 0 and 10 provides a bijection with length-(n+1) tilings; the inverse expands tiles and removes the final zero.

For an optimal-cost recurrence, a recursive construction proves an upper bound. To assert it equals the minimum, prove a matching lower bound on every legal solution. This extra step matters in Towers of Hanoi. Transfer: derive P8's bijection and explicitly justify its empty case, then solve P9.

After your attempt use practice feedback and model contracts to check the argument.