Recurrence relations

Many counting problems are easiest to solve not all at once but in terms of smaller versions of themselves. How many moves does it take to transfer a tower of 10 disks? Exactly twice as many as for 9 disks, plus one. How many bit strings of length 20 have no two consecutive 1s? As many as of length 19, plus as many as of length 18. Equations of this kind, which express each term of a sequence through earlier terms, are called recurrence relations. They are the discrete counterpart of differential equations, and they are the natural language for algorithms that work by breaking a problem into smaller pieces.

This lesson shows how to set up recurrences for counting problems and how to solve the simplest ones by unrolling them and proving the result by induction. Lesson 6 gives a general method for the important family of linear recurrences with constant coefficients.

Sequences defined by recurrence

A recurrence relation for a sequence \(a_0, a_1, a_2, \dots\) is an equation that expresses \(a_n\) in terms of one or more earlier terms, valid for all \(n\) from some point on. Initial conditions give the first few terms. Together they determine the sequence completely: the initial conditions fix the start, and the recurrence then computes each term from the ones before it. For example,

\[ a_n = 3a_{n-1} - 2, \qquad a_0 = 2 \]

gives \(a_1 = 4\), \(a_2 = 10\), \(a_3 = 28\), \(a_4 = 82\). The same recurrence with \(a_0 = 1\) gives the constant sequence 1, 1, 1, ..., so the initial conditions matter as much as the recurrence. A closed form is a formula for \(a_n\) directly in terms of \(n\), with no reference to earlier terms. Here the closed form is \(a_n = 3^n + 1\), which you can check satisfies both the recurrence and the initial condition. Finding closed forms is the main goal of the next two lessons, but a recurrence is already useful in itself: a computer can evaluate it quickly, and it often reveals the structure of a problem better than a formula does.

The Tower of Hanoi

The Tower of Hanoi puzzle, invented by the French mathematician Édouard Lucas in 1883, has three pegs and \(n\) disks of different sizes stacked on the first peg, largest at the bottom. The goal is to move the whole stack to the third peg, one disk at a time, never placing a larger disk on a smaller one. What is the least number of moves?

Let \(H_n\) be the least number of moves for \(n\) disks. The largest disk must move at some point, and when it does, the other \(n - 1\) disks must all be stacked on the remaining peg, because they cannot be on the peg the largest disk leaves or the peg it lands on. Getting them there takes at least \(H_{n-1}\) moves. After the largest disk moves, the \(n - 1\) smaller disks must be moved onto it, taking at least \(H_{n-1}\) more. So \(H_n \ge 2H_{n-1} + 1\), and the strategy just described achieves this. Therefore

\[ H_n = 2H_{n-1} + 1, \qquad H_1 = 1. \]

Unrolling the recurrence: \(H_1 = 1\), \(H_2 = 3\), \(H_3 = 7\), \(H_4 = 15\). These are one less than powers of 2, so we guess \(H_n = 2^n - 1\) and prove it by induction. The base case \(H_1 = 1 = 2^1 - 1\) holds. If \(H_{n-1} = 2^{n-1} - 1\), then \(H_n = 2(2^{n-1} - 1) + 1 = 2^n - 1\). A legend that accompanied the puzzle told of priests moving 64 golden disks; at one move per second, \(2^{64} - 1\) moves would take about 585 billion years.

def hanoi(n, source, target, spare, moves):
    if n == 0:
        return
    hanoi(n - 1, source, spare, target, moves)
    moves.append((n, source, target))
    hanoi(n - 1, spare, target, source, moves)

moves = []
hanoi(3, "A", "C", "B", moves)
for disk, s, t in moves:
    print(f"move disk {disk} from {s} to {t}")

for n in range(1, 11):
    m = []
    hanoi(n, "A", "C", "B", m)
    print(n, len(m), 2 ** n - 1)

move disk 1 from A to C
move disk 2 from A to B
move disk 1 from C to B
move disk 3 from A to C
move disk 1 from B to A
move disk 2 from B to C
move disk 1 from A to C
1 1 1
2 3 3
3 7 7
4 15 15
5 31 31
6 63 63
7 127 127
8 255 255
9 511 511
10 1023 1023

Unrolling a recurrence

For first-order recurrences, where each term depends only on the one before, we can often find the closed form by substituting the recurrence into itself repeatedly, a method called unrolling or iteration. For the Tower of Hanoi:

\[ H_n = 2H_{n-1} + 1 = 2(2H_{n-2} + 1) + 1 = 4H_{n-2} + 2 + 1 = 8H_{n-3} + 4 + 2 + 1 = \cdots = 2^{n-1}H_1 + (2^{n-2} + \cdots + 2 + 1). \]

With \(H_1 = 1\) this is the geometric sum \(1 + 2 + \cdots + 2^{n-1} = 2^n - 1\). Unrolling is reliable for recurrences of the form \(a_n = c\,a_{n-1} + f(n)\). The answer is a sum, which may or may not have a simple form. Once a closed form is found, an induction proof confirms it.

Fibonacci numbers

In his book Liber Abaci of 1202, Leonardo of Pisa, later called Fibonacci, posed a problem about rabbits. A pair of newborn rabbits matures in one month and from then on produces a new pair every month; no rabbit dies. How many pairs are there after \(n\) months? The pairs alive in month \(n\) are the pairs alive in month \(n - 1\), plus the newborns, of which there is one for each pair at least a month old, that is, one for each pair alive in month \(n - 2\). So the number \(F_n\) of pairs satisfies

\[ F_n = F_{n-1} + F_{n-2}, \qquad F_1 = F_2 = 1, \]

giving 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... It is convenient to set \(F_0 = 0\), which is consistent with the recurrence. The rabbits are a fanciful model, but the Fibonacci numbers count a surprising number of things, and the recurrence is the reason. Whenever a structure of size \(n\) is built by adding either a piece of size 1 to a structure of size \(n - 1\) or a piece of size 2 to a structure of size \(n - 2\), the counts satisfy the Fibonacci recurrence.

Domino tilings. In how many ways \(T_n\) can a \(2 \times n\) strip be tiled with \(1 \times 2\) dominoes? Look at the left end. Either a single domino stands upright there, leaving a \(2 \times (n-1)\) strip, or two dominoes lie flat one above the other, leaving a \(2 \times (n - 2)\) strip. These cases are disjoint and cover everything, so \(T_n = T_{n-1} + T_{n-2}\), with \(T_1 = 1\) and \(T_2 = 2\). Hence \(T_n = F_{n+1}\).

Bit strings without consecutive 1s. Let \(b_n\) be the number of bit strings of length \(n\) with no two adjacent 1s. Such a string either ends in 0, preceded by any valid string of length \(n - 1\), or ends in 01, preceded by any valid string of length \(n - 2\). The string cannot end in 11. So \(b_n = b_{n-1} + b_{n-2}\), with \(b_1 = 2\) (0 and 1) and \(b_2 = 3\) (00, 01, 10). Hence \(b_n = F_{n+2}\). This count matters in coding theory, where a rule forbidding consecutive 1s is used in some ways of recording data.

from itertools import product
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

def no_adjacent_ones(n):
    return sum(1 for s in product("01", repeat=n) if "11" not in "".join(s))

def tilings(n):
    # count tilings of a 2-by-n strip by brute-force recursion
    if n <= 1:
        return 1
    return tilings(n - 1) + tilings(n - 2)

print(" n  F(n)  strings  F(n+2)  tilings  F(n+1)")
for n in range(1, 13):
    print(f"{n:2d} {fib(n):5d} {no_adjacent_ones(n):8d} {fib(n+2):7d} {tilings(n):8d} {fib(n+1):7d}")
print("F(100) =", fib(100))

 n  F(n)  strings  F(n+2)  tilings  F(n+1)
 1     1        2       2        1       1
 2     1        3       3        2       2
 3     2        5       5        3       3
 4     3        8       8        5       5
 5     5       13      13        8       8
 6     8       21      21       13      13
 7    13       34      34       21      21
 8    21       55      55       34      34
 9    34       89      89       55      55
10    55      144     144       89      89
11    89      233     233      144     144
12   144      377     377      233     233
F(100) = 354224848179261915075

A word of caution about computing recurrences. The definition of fib above calls itself twice, so without the cache line it would recompute the same values over and over, taking about \(F_n\) steps to compute \(F_n\), which is hopeless for \(n = 100\). With the cache, or with a simple loop that keeps the last two values, each value is computed once. This is the idea of dynamic programming, which CMPUT-204 studies in detail.

Setting up a recurrence

The skill in this lesson is setting up the recurrence, and the method is always the same. Describe the objects of size \(n\). Look at one end, or at one special element, and split the objects into cases according to what happens there. In each case, recognize what remains as an object of a smaller size. Check that the cases are disjoint and cover every object. Then write the recurrence and work out enough initial conditions to start it, being careful that the recurrence is valid for every \(n\) above them.

Recurrences in algorithms

Recursive algorithms lead naturally to recurrences for their running times. Binary search on a sorted list of \(n\) items compares the target with the middle item and continues in one half, so the number of comparisons satisfies roughly \(C(n) = C(n/2) + 1\), giving about \(\log_2 n\) comparisons. Merge sort sorts each half recursively and merges the results with about \(n\) comparisons, so \(T(n) = 2T(n/2) + n\), whose solution grows like \(n \log_2 n\). These divide-and-conquer recurrences, which involve \(n/2\) rather than \(n - 1\), are studied in CMPUT-204. The recurrences in this course have the form \(a_n\) in terms of \(a_{n-1}, a_{n-2}, \dots\), which suits counting problems.