Recurrence Relations and Generating Functions

Many counting problems are easiest to solve by relating the answer for size n to the answers for smaller sizes. Such a recurrence relation, together with initial conditions, determines the whole sequence.

Setting up a recurrence

Binary strings of length n with no two consecutive 0s. A valid string either ends in 1 (any valid string of length n − 1, then 1) or ends in 10 (any valid string of length n − 2, then 10). So f(n) = f(n − 1) + f(n − 2) with f(1) = 2 and f(2) = 3: the sequence 2, 3, 5, 8, 13, 21, … (Fibonacci numbers), and f(10) = 144.

Other classic recurrences:

Linear homogeneous recurrences with constant coefficients

For aₙ = c₁aₙ₋₁ + c₂aₙ₋₂, try aₙ = rⁿ. This gives the characteristic equation

r² − c₁r − c₂ = 0.

• Distinct roots r₁, r₂: aₙ = A·r₁ⁿ + B·r₂ⁿ.
• Repeated root r: aₙ = (A + B·n)·rⁿ.

Find A and B from the initial conditions. (Higher orders work the same way, with one term per root, and a root of multiplicity m contributing (A₀ + A₁n + … + A_m−1n^m−1)rⁿ.)

Example 1. aₙ = 5aₙ₋₁ − 6aₙ₋₂, a₀ = 1, a₁ = 4. The characteristic equation r² − 5r + 6 = 0 has roots 2 and 3, so aₙ = A·2ⁿ + B·3ⁿ. From A + B = 1 and 2A + 3B = 4: B = 2, A = −1. So aₙ = 2·3ⁿ − 2ⁿ.

Example 2. aₙ = 4aₙ₋₁ − 4aₙ₋₂, a₀ = 1, a₁ = 6. The root 2 is repeated, so aₙ = (A + Bn)2ⁿ. A = 1, and (1 + B)·2 = 6 gives B = 2. So aₙ = (1 + 2n)·2ⁿ.

The closed forms agree with the recurrences term by term:

def iterate(c1, c2, a0, a1, n):
    seq = [a0, a1]
    while len(seq) < n:
        seq.append(c1 * seq[-1] + c2 * seq[-2])
    return seq

print(iterate(5, -6, 1, 4, 8))
print([2 * 3 ** n - 2 ** n for n in range(8)])
print(iterate(4, -4, 1, 6, 8))
print([(1 + 2 * n) * 2 ** n for n in range(8)])

[1, 4, 14, 46, 146, 454, 1394, 4246]
[1, 4, 14, 46, 146, 454, 1394, 4246]
[1, 6, 20, 56, 144, 352, 832, 1920]
[1, 6, 20, 56, 144, 352, 832, 1920]

Non-homogeneous recurrences

For aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + f(n), the solution is the general homogeneous solution plus one particular solution. Guess the particular solution in the form of f(n): a constant for a constant, a polynomial of the same degree for a polynomial, C·sⁿ for sⁿ (multiplied by n if s is a root of the characteristic equation).

Example: T(n) = 2T(n − 1) + 1. Homogeneous part: A·2ⁿ. Particular solution: try a constant c, so c = 2c + 1 and c = −1. T(n) = A·2ⁿ − 1, and T(1) = 1 gives A = 1: T(n) = 2ⁿ − 1.

Generating functions

The generating function of a sequence a₀, a₁, a₂, … is the power series G(x) = a₀ + a₁x + a₂x² + …. Counting problems turn into algebra:

To count solutions of x₁ + x₂ + x₃ = 10 with xᵢ ≥ 0, find the coefficient of x¹⁰ in (1 + x + x² + …)³ = 1/(1 − x)³: C(12, 2) = 66, the stars-and-bars answer. Restrictions change the factors: if x₁ must be even, its factor becomes 1 + x² + x⁴ + ….

Catalan numbers

The Catalan numbers Cₙ = C(2n, n) / (n + 1) = 1, 1, 2, 5, 14, 42, 132, … satisfy Cₙ₊₁ = Σᵢ Cᵢ Cₙ₋ᵢ. They count:

• binary search trees (or binary tree shapes) with n nodes,
• ways to fully parenthesise a product of n + 1 factors (the parse trees of an ambiguous expression grammar, from the compiler lessons),
• balanced strings of n pairs of parentheses,
• triangulations of a convex polygon with n + 2 sides.

Practice questions