Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 36 ยท Recurrences and Generating Functions

Recurrence Relations

Learn how to count by building a recurrence relation: set up a_n from smaller cases, check it by brute force, and meet Tower of Hanoi, tilings and line regions.

Some counting problems have no neat product or binomial formula, but they do have a pattern: the answer for size n can be built from the answers for smaller sizes. A rule that expresses a_n through earlier terms is called a recurrence relation. Together with a few starting values (the initial conditions), it determines the whole sequence.

Recurrences are the bridge between the counting rules of the earlier chapters and the algebra tools of this one. In this lesson you learn the habit of mind: look at the last step, split into cases, count each case with smaller instances. The next lessons show how to solve the recurrences you find (linear recurrences and generating functions).

The recipe

  1. Define a_n precisely (what exactly is being counted, for size n).
  2. Pick a "last decision": the last disk moved, the last tile placed, the last bit written.
  3. Split into cases that are disjoint and cover everything (sum rule).
  4. In each case, what remains is a smaller instance of the same problem (product rule if several choices combine).
  5. Write the initial values by hand and test the recurrence on small n by brute force.

Step 5 is not optional. A recurrence that looks right is wrong surprisingly often.

Example 1: Tower of Hanoi

To move n disks from peg A to peg C, you must move the top n-1 disks away (to B), move the largest disk (1 move), then move the n-1 disks onto it. So a_n = 2 a_{n-1} + 1 with a_0 = 0. Unrolling gives a_n = 2^n - 1.

Example 2: tilings

How many ways can a 1 x n strip be covered with 1 x 1 squares and 1 x 2 dominoes? Look at the last cell. It is covered either by a square (the rest is a strip of length n-1) or by the right half of a domino (the rest is a strip of length n-2). So a_n = a_{n-1} + a_{n-2}, with a_0 = 1 (the empty tiling) and a_1 = 1. These are the Fibonacci numbers.

Python Hanoi and tilings

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop version tilings takes n steps. The naive recursion brute recomputes the same values again and again (exponential time), which is why hanoi uses lru_cache to remember results. A recurrence is also an algorithm: this is exactly dynamic programming.

Example 3: bit strings with no two 1s in a row

Let a_n be the number of binary strings of length n that never contain 11. Look at the first bit. If it is 0, the remaining n-1 bits are any valid string: a_{n-1} ways. If it is 1, the next bit must be 0, and the remaining n-2 bits are free: a_{n-2} ways. Again a_n = a_{n-1} + a_{n-2}, but now the start is a_1 = 2, a_2 = 3. Same rule, different initial conditions, different sequence (shifted Fibonacci).

Example 4: regions cut by lines

n lines in general position (no two parallel, no three through one point) cut the plane into r_n regions. The n-th line crosses the previous n-1 lines in n-1 points, which splits it into n pieces, and each piece divides an old region in two. So r_n = r_{n-1} + n, r_0 = 1, giving r_n = (n^2 + n + 2)/2.

Python Check recurrences by brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

flowchart TD
    A["a(n): strings of length n with no 11"] --> B["first bit 0: a(n-1) ways"]
    A --> C["first bit 1, then 0: a(n-2) ways"]
    B --> D["a(n) = a(n-1) + a(n-2)"]
    C --> D

Splitting on the first bit gives two disjoint cases, each a smaller copy of the same problem.

The most common mistake is overlapping cases (counting a string in two branches) or missing cases (forgetting a state the last step can be in). Always test the first six values by brute force.

Kinds of recurrences

  • First order: a_n depends on a_{n-1} only, such as Hanoi.
  • Linear, constant coefficients: a_n = c_1 a_{n-1} + ... + c_k a_{n-k}; solved in the next lesson.
  • Full history: a_n depends on all earlier terms, such as the Catalan recurrence.
  • Two indices: Pascal's rule and Stirling numbers.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A 1 x n strip is tiled with 1x1 squares and 1x2 dominoes. Which recurrence counts the tilings?

    The last cell is covered by a square (leaving n-1 cells) or by half a domino (leaving n-2 cells).
  2. 2. For Tower of Hanoi, a(n) = 2 a(n-1) + 1 and a(0) = 0. What is a(5)?

    The sequence is 0, 1, 3, 7, 15, 31, so a(5) = 31 = 2^5 - 1.
  3. 3. Why must you state initial conditions?

    The tiling and no-11 problems share a recurrence but differ in their initial values, so they give different sequences.
  4. 4. How many binary strings of length 4 contain no two adjacent 1s?

    a(1)=2, a(2)=3, a(3)=5, a(4)=8.

Summary

  • A recurrence expresses a_n through earlier terms; initial conditions fix the sequence.
  • Find it by splitting on the last (or first) decision into disjoint cases that each leave a smaller instance.
  • Tower of Hanoi: 2^n - 1; tilings and no-11 strings: Fibonacci-type; n lines: (n^2+n+2)/2.
  • Always verify the first values by brute force; code the recurrence as a loop or with memoization.

Next: Solving Linear Recurrences