# Recurrence Relations — Setting Them Up, Solving Linear Recurrences, and the Master Theorem for Algorithms

Source: https://skills101.in/learn/discrete-math/recurrence-relations — Skills101 free tutorial (Discrete Mathematics). Updated 2026-11-09.

A **recurrence relation** defines each term of a sequence using earlier terms: aₙ = aₙ₋₁ + aₙ₋₂. Recurrences are how we count recursive structures and how we analyse **recursive algorithms** — merge sort, binary search, divide and conquer. This is where discrete maths meets DSA directly.

## 1. Modelling with recurrences

**Tower of Hanoi.** Move n disks: move n−1 to the spare peg, move the biggest, move n−1 back on top. So **Hₙ = 2Hₙ₋₁ + 1**, H₁ = 1.

**Tiling a 2×n board with 2×1 dominoes.** The first column is either one vertical domino (leaving 2×(n−1)) or two horizontal dominoes (leaving 2×(n−2)). So **Tₙ = Tₙ₋₁ + Tₙ₋₂** — Fibonacci again.

**Binary strings of length n with no two consecutive 1s.** Ends in 0 → any valid string of length n−1 plus 0; ends in 1 → must be "…01" → valid string of length n−2 plus 01. So **Bₙ = Bₙ₋₁ + Bₙ₋₂**, B₁ = 2, B₂ = 3.

![Tiling a 2 by n board: either place one vertical domino, leaving a 2 by n-1 board, or two horizontal dominoes, leaving a 2 by n-2 board, so T(n) = T(n-1) + T(n-2)](https://skills101.in/learn-img/discrete-math/tiling-recurrence.svg)

Check the binary-strings recurrence against brute force:

```python
from itertools import product

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

def recur(n):
    a, b = 2, 3                 # B1, B2
    if n == 1: return a
    for _ in range(n - 2):
        a, b = b, a + b
    return b

print([brute(n) for n in range(1, 11)])
print([recur(n) for n in range(1, 11)])
```

```text
[2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
[2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
```

## 2. Solving linear homogeneous recurrences

Form: aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ (constant coefficients, no extra term).

1. Write the **characteristic equation**: r² = c₁r + c₂.
2. Find roots r₁, r₂.
3. **Distinct roots:** aₙ = A·r₁ⁿ + B·r₂ⁿ. **Repeated root r:** aₙ = (A + Bn)·rⁿ.
4. Use the initial conditions to find A and B.

**Example:** aₙ = 5aₙ₋₁ − 6aₙ₋₂, a₀ = 1, a₁ = 4.
r² − 5r + 6 = 0 → r = 2, 3. So aₙ = A·2ⁿ + B·3ⁿ. a₀: A + B = 1; a₁: 2A + 3B = 4 → B = 2, A = −1.
So **aₙ = −2ⁿ + 2·3ⁿ**. Check both ways:

```python
def by_recurrence(n):
    a = [1, 4]
    for i in range(2, n + 1):
        a.append(5 * a[i - 1] - 6 * a[i - 2])
    return a[n]

closed = lambda n: -(2 ** n) + 2 * 3 ** n
print([by_recurrence(n) for n in range(8)])
print([closed(n) for n in range(8)])
```

```text
[1, 4, 14, 46, 146, 454, 1394, 4246]
[1, 4, 14, 46, 146, 454, 1394, 4246]
```

**Fibonacci** (Fₙ = Fₙ₋₁ + Fₙ₋₂) has roots (1 ± √5)/2, giving **Binet's formula** Fₙ = (φⁿ − ψⁿ)/√5 with φ ≈ 1.618 — so Fibonacci numbers grow exponentially, ~1.618ⁿ, which is why naive recursive Fibonacci is so slow.

## 3. Non-homogeneous recurrences

aₙ = c·aₙ₋₁ + f(n): solution = (homogeneous solution) + (a particular solution).

**Tower of Hanoi:** Hₙ = 2Hₙ₋₁ + 1. Homogeneous part: A·2ⁿ. Try a constant particular solution p: p = 2p + 1 → p = −1. So Hₙ = A·2ⁿ − 1; H₁ = 1 gives A = 1. **Hₙ = 2ⁿ − 1.**

```python
def hanoi_moves(n, src="A", dst="C", via="B", moves=None):
    if moves is None: moves = []
    if n == 0: return moves
    hanoi_moves(n - 1, src, via, dst, moves)
    moves.append((src, dst))
    hanoi_moves(n - 1, via, dst, src, moves)
    return moves

for n in range(1, 8):
    print(n, len(hanoi_moves(n)), 2 ** n - 1)
print("first moves for 3 disks:", hanoi_moves(3))
```

```text
1 1 1
2 3 3
3 7 7
4 15 15
5 31 31
6 63 63
7 127 127
first moves for 3 disks: [('A', 'C'), ('A', 'B'), ('C', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('A', 'C')]
```

64 disks would need 2⁶⁴ − 1 ≈ 1.8 × 10¹⁹ moves — the legend's priests are safe for a very long time.

## 4. Recurrences for algorithms

Divide-and-conquer algorithms give recurrences of the form **T(n) = a·T(n/b) + f(n)**: *a* subproblems, each of size *n/b*, plus *f(n)* work to split/combine.

| Algorithm | Recurrence | Solution |
|---|---|---|
| Binary search | T(n) = T(n/2) + O(1) | O(log n) |
| Merge sort | T(n) = 2T(n/2) + O(n) | O(n log n) |
| Tree traversal (balanced) | T(n) = 2T(n/2) + O(1) | O(n) |
| Karatsuba multiplication | T(n) = 3T(n/2) + O(n) | O(n^1.585) |
| Linear recursion (e.g. factorial) | T(n) = T(n−1) + O(1) | O(n) |

## 5. The Master Theorem

For T(n) = a·T(n/b) + Θ(nᵈ) with a ≥ 1, b > 1, compare **d** with **log_b a**:

| Case | Condition | T(n) |
|---|---|---|
| 1 | d < log_b a (splitting dominates) | Θ(n^(log_b a)) |
| 2 | d = log_b a (balanced) | Θ(nᵈ log n) |
| 3 | d > log_b a (combine work dominates) | Θ(nᵈ) |

![Master theorem as a recursion tree: compare the work at the leaves, n to the log base b of a, with the work at the root, n to the d; whichever dominates decides the total, and if they are equal every level does equal work giving an extra log n factor](https://skills101.in/learn-img/discrete-math/master-theorem.svg)

```python
import math

def master(a, b, d):
    crit = math.log(a, b)
    if abs(d - crit) < 1e-9:
        return f"Theta(n^{d} log n)"
    if d < crit:
        return f"Theta(n^{crit:.3f})"
    return f"Theta(n^{d})"

for name, a, b, d in [("binary search", 1, 2, 0), ("merge sort", 2, 2, 1),
                      ("Karatsuba", 3, 2, 1), ("T(n)=8T(n/2)+n^2", 8, 2, 2), ("T(n)=2T(n/2)+n^2", 2, 2, 2)]:
    print(f"{name:18} -> {master(a, b, d)}")
```

```text
binary search      -> Theta(n^0 log n)
merge sort         -> Theta(n^1 log n)
Karatsuba          -> Theta(n^1.585)
T(n)=8T(n/2)+n^2   -> Theta(n^3.000)
T(n)=2T(n/2)+n^2   -> Theta(n^2)
```

(Binary search's "n^0 log n" is just Θ(log n).) The Master Theorem doesn't cover everything — e.g. T(n) = T(n−1) + n (use the substitution/unrolling method: Θ(n²)).

## Common mistakes

- Forgetting initial conditions (a recurrence alone doesn't define a sequence).
- Using A·rⁿ + B·rⁿ for a **repeated** root (it must be (A + Bn)rⁿ).
- Applying the Master Theorem to T(n) = T(n − 1) + … (not of the form T(n/b)).
- Mixing up a and b (a = number of subproblems, b = shrink factor).

## Quick recap

- Model by thinking about the **first/last step** (Hanoi, tiling, strings).
- Linear homogeneous: characteristic equation; distinct roots A·r₁ⁿ + B·r₂ⁿ, repeated (A + Bn)rⁿ.
- Non-homogeneous: homogeneous + particular solution (Hanoi = 2ⁿ − 1).
- Master Theorem: compare d with log_b a → Θ(n^(log_b a)), Θ(nᵈ log n) or Θ(nᵈ).


Practice quiz and free certificate: https://skills101.in/learn/discrete-math/recurrence-relations