Chapter 19 of 30

Recurrence Relations

Some counting problems are hard to attack head-on but easy to attack one step at a time. How many bit strings of length 20 have no two consecutive 0s? Listing them is hopeless, and there is no obvious formula. But if we know the answers for lengths 19 and 18, the answer for length 20 follows in one line. Such a step-by-step description is a recurrence relation.

Recurrences are everywhere in computer science: the running time of merge sort, the number of moves in the Tower of Hanoi, the number of binary search trees, dynamic programming tables. This chapter shows how to set up a recurrence from a problem, how to classify it, and how to solve simple ones by unrolling. The systematic method for linear recurrences comes in the next chapter, Solving Linear Recurrences.

A recurrence relation for a sequence a0, a1, a2, … is an equation that expresses an in terms of one or more earlier terms a0, …, an−1, for all n beyond some starting point. The initial conditions give the values of the first few terms. A solution is a sequence (preferably a closed formula for an) that satisfies both.

Every sequence and closed form in this chapter was checked by computing the terms from the recurrence and comparing with a brute-force count or the formula.


Recurrences and Induction

A recurrence is the counting cousin of Mathematical Induction. Induction proves P(n) using P(n − 1); a recurrence computes an using an−1. Both need a starting point:

  • The recurrence an = 2an−1 alone does not determine the sequence: 1, 2, 4, 8, … and 3, 6, 12, 24, … both satisfy it.

  • With the initial condition a0 = 3, the sequence is fixed: an = 3 × 2n.

In general, a recurrence that uses the previous k terms needs k initial conditions. This is exactly why a recursive function needs base cases.


Modelling with Recurrences

The skill is to split the objects of size n by what happens at the last (or first) step, so that each case reduces to a smaller object of the same kind.

1. Compound interest

₹10,000 is deposited at 8% interest compounded yearly. Let an be the amount after n years. Each year the amount grows by 8%:

an = 1.08 an−1, a0 = 10000, so an = 10000 × 1.08n. After 5 years: about ₹14,693.28.

2. Tower of Hanoi

n discs of different sizes sit on peg A, largest at the bottom. Move them all to peg C, one disc at a time, never placing a larger disc on a smaller one. Let Hn be the minimum number of moves.

The largest disc must move at some point, and at that moment the other n − 1 discs must all be stacked on the third peg. So the best plan is:

  1. Move the top n − 1 discs from A to B: Hn−1 moves.

  2. Move the largest disc from A to C: 1 move.

  3. Move the n − 1 discs from B to C: Hn−1 moves.

So Hn = 2Hn−1 + 1 with H1 = 1. Terms: 1, 3, 7, 15, 31, …

3. Bit strings with no two consecutive 0s

Let an count bit strings of length n with no "00". Split by the last bit:

  • Ends in 1: the first n − 1 bits can be any valid string: an−1 strings.

  • Ends in 0: then the bit before it must be 1 (otherwise we get 00), so the string ends in "10", and the first n − 2 bits are any valid string: an−2 strings.

So an = an−1 + an−2 for n ≥ 3, with a1 = 2 (0, 1) and a2 = 3 (01, 10, 11). Terms: 2, 3, 5, 8, 13, 21, 34, 55, … These are Fibonacci numbers: an = Fn+2, where F1 = F2 = 1.

4. Climbing stairs (a favourite interview question)

You climb a staircase of n steps, taking 1 or 2 steps at a time. Let sn be the number of ways. The last move is either a 1-step (from step n − 1) or a 2-step (from step n − 2), so sn = sn−1 + sn−2, with s0 = 1 (do nothing) and s1 = 1. For 10 steps: 89 ways. The same recurrence counts tilings of a 2 × n board by 1 × 2 dominoes: the last column is either one vertical domino or the last two columns hold two horizontal dominoes.

5. Decimal strings with an even number of 0s

Let an be the number of decimal strings (digits 0 to 9) of length n with an even number of 0s. Split by the last digit:

  • Last digit non-zero (9 choices): the first n − 1 digits must have an even number of 0s: 9an−1.

  • Last digit 0: the first n − 1 digits must have an odd number of 0s. There are 10n−1 strings of length n − 1, so 10n−1 − an−1 of them.

So an = 8an−1 + 10n−1, a1 = 9. Terms: 9, 82, 756, 7048, … (We solve this in Solving Linear Recurrences.)

6. Regions made by lines

n lines are drawn in the plane, no two parallel and no three through one point. Let Ln be the number of regions. The n-th line crosses the previous n − 1 lines at n − 1 different points, which cut it into n pieces. Each piece splits one old region into two, adding n regions:

Ln = Ln−1 + n, L0 = 1. Terms: 1, 2, 4, 7, 11, 16, …

7. Derangements

In Inclusion-Exclusion Principle we found Dn, the permutations with no fixed point, using a formula. A recurrence is also possible. Look at where element 1 goes: some position k ≠ 1 (n − 1 choices). Now ask where element k goes:

  • k goes to position 1 (1 and k swap): the other n − 2 elements must be deranged: Dn−2.

  • k does not go to position 1: then, treating position 1 as k's forbidden spot, the n − 1 elements other than 1 must form a derangement: Dn−1.

So Dn = (n − 1)(Dn−1 + Dn−2), D1 = 0, D2 = 1. Terms: 0, 1, 2, 9, 44, 265, 1854, matching the formula.

8. Catalan numbers

How many binary search trees can be built from the keys 1, 2, …, n? Let Cn be the count, with C0 = 1 (the empty tree). If key i is the root, keys 1…i − 1 form the left subtree (Ci−1 shapes) and keys i + 1…n the right subtree (Cn−i shapes). By the product and sum rules:

Cn = ∑i=1n Ci−1 Cn−i, C0 = 1. Terms: 1, 1, 2, 5, 14, 42, 132, 429, …

This recurrence uses all earlier terms, not a fixed number of them, and it is not linear. The same numbers count balanced strings of n pairs of parentheses, ways to fully parenthesise a product of n + 1 matrices, and triangulations of a convex polygon with n + 2 sides. The closed form Cn = C(2n, n)/(n + 1) is obtained later, in Generating Functions; for now the recurrence is enough to compute the terms.


Classifying Recurrences

Term

Meaning

Example

Order (degree)

How far back it reaches: an depends on an−1, …, an−k

an = an−1 + an−2 has order 2

Linear

Earlier terms appear only to the first power, multiplied by coefficients, never multiplied together

Linear: an = 3an−1 + n. Not linear: an = an−12, Cn = ∑ Ci−1Cn−i

Homogeneous

No term free of the a's; the all-zero sequence is a solution

Homogeneous: an = 2an−1. Non-homogeneous: Hn = 2Hn−1 + 1

Constant coefficients

The multipliers of earlier terms do not depend on n

Constant: an = 5an−1 − 6an−2. Not: Dn = (n − 1)(Dn−1 + Dn−2)

Divide-and-conquer

an depends on a term like an/b, a fraction of n

T(n) = 2T(n/2) + n (merge sort)

The most important class in exams is linear recurrences with constant coefficients. The homogeneous ones can always be solved by the characteristic equation method of the next chapter, and the non-homogeneous ones can be solved the same way when the extra term is a common type such as a polynomial or an exponential like 3n.


Solving by Iteration (Unrolling)

For simple first-order recurrences, substitute the recurrence into itself until a pattern appears, then sum the pattern. Always confirm the guess by induction.

Tower of Hanoi

H(n) = 2 H(n−1) + 1
     = 2 [2 H(n−2) + 1] + 1          = 2² H(n−2) + 2 + 1
     = 2² [2 H(n−3) + 1] + 2 + 1     = 2³ H(n−3) + 2² + 2 + 1
     ...
     = 2^(n−1) H(1) + 2^(n−2) + … + 2 + 1
     = 2^(n−1) + 2^(n−2) + … + 2 + 1   = 2^n − 1

Proof by induction that Hn = 2n − 1. Base: H1 = 1 = 21 − 1. Step: if Hn−1 = 2n−1 − 1, then Hn = 2(2n−1 − 1) + 1 = 2n − 1. ∎ (Legend says monks are moving 64 discs; at one move per second that is 264 − 1 seconds, about 585 billion years.)

Regions made by lines

Ln = Ln−1 + n = Ln−2 + (n − 1) + n = … = L0 + (1 + 2 + … + n) = 1 + n(n + 1)/2. Check: 4 lines give 1 + 10 = 11 regions.

Divide-and-conquer recurrences

Merge sort splits n items into two halves, sorts each recursively, and merges in about n steps: T(n) = 2T(n/2) + n, T(1) = 1. Take n = 2k so the halves are always whole numbers:

T(n) = 2 T(n/2) + n
     = 2 [2 T(n/4) + n/2] + n       = 4 T(n/4) + 2n
     = 4 [2 T(n/8) + n/4] + 2n      = 8 T(n/8) + 3n
     ...
     = 2^k T(n/2^k) + k·n           (after k steps, n/2^k = 1)
     = n · T(1) + n log₂ n          = n log₂ n + n

For n = 1024 this gives 1024 × 10 + 1024 = 11264. Binary search does one comparison and recurses on half: T(n) = T(n/2) + 1, T(1) = 1, which unrolls to T(n) = log2 n + 1 (11 comparisons for n = 1024).

The Master Theorem (for reference)

For T(n) = a T(n/b) + f(n) with constants a ≥ 1, b > 1, compare f(n) with nlogb a:

Case

Condition

Result

Example

1

f(n) = O(nlogb a − ε) for some ε > 0

T(n) = Θ(nlogb a)

T(n) = 8T(n/2) + n2 → Θ(n3)

2

f(n) = Θ(nlogb a)

T(n) = Θ(nlogb a log n)

Merge sort 2T(n/2) + n → Θ(n log n); binary search T(n/2) + 1 → Θ(log n)

3

f(n) = Ω(nlogb a + ε) for some ε > 0, and a f(n/b) ≤ c f(n) for some c < 1 and large n

T(n) = Θ(f(n))

T(n) = 2T(n/2) + n2 → Θ(n2)

The master theorem gives only the order of growth, not an exact formula, and it does not cover every case (for example T(n) = 2T(n/2) + n/log n falls in a gap between cases 1 and 2). Exact solutions come from unrolling or from the change of variable n = 2k shown in the next chapter.


Recurrences in Code

A recurrence translates directly into a recursive function, and the initial conditions become base cases. The program below counts the "no 00" strings with the recurrence and compares against brute force, then checks the Hanoi formula.

from functools import lru_cache
from itertools import product

# a(n) = number of bit strings of length n with no two consecutive 0s
@lru_cache(maxsize=None)
def a(n):
    if n == 1:
        return 2          # "0", "1"
    if n == 2:
        return 3          # "01", "10", "11"
    return a(n - 1) + a(n - 2)

def brute(n):
    return sum(1 for bits in product("01", repeat=n) if "00" not in "".join(bits))

for n in range(1, 11):
    print(n, a(n), brute(n))

# Tower of Hanoi: H(n) = 2 H(n-1) + 1, H(1) = 1, compared with 2^n - 1
h = 1
for n in range(2, 11):
    h = 2 * h + 1
print("H(10) =", h, " 2^10 - 1 =", 2 ** 10 - 1)

Output:

1 2 2
2 3 3
3 5 5
4 8 8
5 13 13
6 21 21
7 34 34
8 55 55
9 89 89
10 144 144
H(10) = 1023  2^10 - 1 = 1023

The @lru_cache line matters. Without it, computing a(n) recursively calls a(n − 1) and a(n − 2), which call their own predecessors again and again: the number of calls itself grows like the Fibonacci numbers, which is exponential. With caching (memoization) each a(k) is computed once, so the work is O(n). This is the core idea of dynamic programming: a recurrence plus a table of stored answers.


Common Mistakes

  • Missing or wrong initial conditions. A second-order recurrence needs two. For the "no 00" strings, a1 = 2 and a2 = 3; starting from a0 instead needs a0 = 1 (the empty string).

  • Cases that overlap or miss objects. Splitting by the last symbol works because every string ends in exactly one symbol. Check that your cases are disjoint and cover everything (the sum rule needs both).

  • Forgetting the restriction carries over. In the "no 00" problem, a string ending in 0 forces the previous bit to be 1; just writing an = 2an−1 ignores this.

  • Calling a recurrence linear when it is not. an = an−1 × an−2 and the Catalan recurrence are non-linear; the characteristic-equation method does not apply to them.

  • Treating the master theorem as an exact formula. It gives Θ-bounds only, and needs a and b to be constants.

  • Implementing recurrences with plain recursion. Exponential time for something that should be linear. Use memoization or an iterative loop.


Practice and GATE-Style Questions

Q1. Find a recurrence for the number of ternary strings (digits 0, 1, 2) of length n with no two consecutive 0s. How many have length 4?

Split by the last digit. Ends in 1 or 2: any valid string of length n − 1 then 1 or 2: 2bn−1. Ends in 0: the previous digit is 1 or 2, so the string ends in "10" or "20" after a valid string of length n − 2: 2bn−2. So bn = 2bn−1 + 2bn−2, b1 = 3, b2 = 8. Then b3 = 22 and b4 = 60.

Q2. You may climb 1, 2 or 3 steps at a time. In how many ways can you climb 7 steps?

tn = tn−1 + tn−2 + tn−3, with t0 = 1, t1 = 1, t2 = 2. Then 4, 7, 13, 24, so t7 = 44.

Q3. Classify: (a) an = 3an−1 + 4an−3, (b) an = n an−1, (c) an = an−1 + an−22, (d) an = 2an−1 + 3n.

(a) Linear, homogeneous, constant coefficients, order 3. (b) Linear, homogeneous, order 1, but the coefficient n is not constant (its solution with a0 = 1 is n!). (c) Not linear because of the square. (d) Linear, order 1, constant coefficients, non-homogeneous (the 3n term).

Q4. How many binary search trees can be formed with 5 distinct keys?

C5 = C0C4 + C1C3 + C2C2 + C3C1 + C4C0 = 14 + 5 + 4 + 5 + 14 = 42.

Q5. Solve T(n) = T(n − 1) + n with T(1) = 1. What algorithm has this behaviour?

Unrolling: T(n) = 1 + 2 + … + n = n(n + 1)/2 = Θ(n2). This is the worst case of quicksort (or selection sort): each step does work proportional to the current size and reduces the problem by only one element.

Q6. Interview: how many function calls does the naive recursive fib(n) make, with base cases fib(0) and fib(1)?

Let c(n) be the number of calls. c(0) = c(1) = 1 and c(n) = 1 + c(n − 1) + c(n − 2). The solution is c(n) = 2Fn+1 − 1 (with F1 = F2 = 1); for example c(5) = 15 = 2 × 8 − 1. Since Fibonacci numbers grow like 1.618n, the naive version is exponential, while memoization makes it linear.


Summary

  • A recurrence relation defines an from earlier terms; the initial conditions pin down one sequence.

  • To build one, split the size-n objects by the last (or first) step into disjoint cases that are smaller copies of the same problem.

  • Classics: Hanoi Hn = 2Hn−1 + 1; no-00 strings and stairs (Fibonacci); regions Ln = Ln−1 + n; derangements Dn = (n − 1)(Dn−1 + Dn−2); Catalan Cn = ∑Ci−1Cn−i.

  • Classify by order, linearity, homogeneity and constant coefficients.

  • Solve simple ones by unrolling and confirm by induction; divide-and-conquer recurrences give n log n, log n and similar growth rates.

A recurrence turns a big counting problem into a small step plus a smaller copy of itself. Find the step, fix the base cases, and the computer or the next chapter does the rest.