Setting Up Recurrence Relations

Core Idea

A recurrence relation defines each term of a sequence in terms of earlier terms, together with initial conditions. The Fibonacci sequence Fₙ = Fₙ₋₁ + Fₙ₋₂ with F₀ = 0, F₁ = 1 is the canonical example. Recurrences arise in counting problems (tilings, paths in a grid), algorithm analysis (merge sort, Tower of Hanoi), and combinatorics. The core skill is recognizing recursive structure in a problem and translating it faithfully into a recurrence equation with correct initial conditions.

How It's Best Learned

Build recurrences from physical problems: domino tiling of a 2×n board, staircase-climbing with 1 or 2 steps, Tower of Hanoi. Draw the recursive decomposition before writing the formula. Verify the recurrence produces correct values for small cases before attempting to solve it.

Common Misconceptions

• Setting up the recurrence correctly but specifying the wrong initial conditions — both parts are required.
• Not verifying the recurrence against small cases.
• Confusing a closed-form (explicit) formula with a recursive definition.

Explainer

A recurrence relation is a rule that defines each term of a sequence using earlier terms. The classic example is the Fibonacci sequence: F₀ = 0, F₁ = 1, and Fₙ = Fₙ₋₁ + Fₙ₋₂ for n ≥ 2. The recurrence equation (Fₙ = Fₙ₋₁ + Fₙ₋₂) tells you how to generate new terms; the initial conditions (F₀ = 0, F₁ = 1) tell you where to start. Without both pieces, the sequence is not determined.

The key skill in this topic is setting up a recurrence from a problem — not just recognizing one. The strategy is to think recursively: suppose you have already solved the problem for smaller inputs. How does the solution for size n relate to solutions for smaller sizes? For domino tiling, you ask: "What are the choices for the first column?" Each choice leaves a smaller board, and the number of ways to complete that board is a value you've already labeled T(k). Writing out those choices and adding them gives you the recurrence. The initial conditions come from the smallest cases you can count by hand.

This process shares deep structure with mathematical induction, which you already know. In induction, you prove a statement for n by assuming it for n-1 (or smaller values). In recurrence setup, you define the count for n by expressing it in terms of counts for smaller values. The recursive decomposition is the same — you're just computing instead of proving.

One pitfall to watch for: getting the initial conditions wrong while getting the recurrence right. For example, if you define T(0) = 0 instead of T(0) = 1 for the tiling problem, every subsequent term will be off. Always verify your recurrence by computing T(1), T(2), and T(3) both from the formula and by direct enumeration. If they disagree, something is wrong — and it is usually the initial conditions.

Finally, resist the temptation to jump immediately to a closed-form formula. A recurrence is a perfectly valid, complete description of a sequence. Techniques for solving recurrences (finding closed forms) come later; the foundational skill here is faithfully capturing recursive structure as an equation.