# Solving Recurrence Relations — Repeated Roots, Particular Solutions, Unrolling and Generating Functions

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

The earlier lesson on [recurrence relations](https://skills101.in/learn/discrete-math/recurrence-relations) showed how to **set up** a recurrence and solve the simplest kinds. University papers and GATE go further: repeated roots, a "+ 2ⁿ" on the right-hand side, recurrences from algorithms that need unrolling. This lesson is a set of fully solved examples. After each one we **check the answer in Python** by computing the sequence both ways. If the two lists match, the closed form is right.

## 1. The general method in one picture

A **closed form** is a formula for aₙ that uses only n, with no earlier terms. To find one for a linear recurrence with constant coefficients:

![Flowchart for solving a recurrence: write the characteristic equation and find its roots; distinct roots give A times r1 to the n plus B times r2 to the n, a repeated root gives A plus Bn times r to the n; if there is an extra term f of n, add a particular solution; finally use the initial values to find the constants and check](https://skills101.in/learn-img/discrete-math/recurrence-method.svg)

1. Solve the **homogeneous** part (drop the extra term f(n)) with the characteristic equation.
2. If there is an extra term, find **one particular solution** that fits it.
3. Add them: aₙ = (homogeneous part) + (particular part).
4. Use the **initial values** to find the unknown constants.
5. **Check** a few terms against the recurrence.

## 2. Repeated root

**Problem:** aₙ = 4aₙ₋₁ − 4aₙ₋₂, with a₀ = 1, a₁ = 6.

- Characteristic equation: r² = 4r − 4, so r² − 4r + 4 = 0, so (r − 2)² = 0. The root **r = 2 is repeated**.
- With a repeated root, the general solution is aₙ = **(A + Bn)·2ⁿ**. (Using A·2ⁿ + B·2ⁿ would only give one free constant, which cannot fit two initial values.)
- a₀ = 1: (A + 0)·1 = 1, so A = 1.
- a₁ = 6: (1 + B)·2 = 6, so B = 2.
- **aₙ = (1 + 2n)·2ⁿ.**

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

closed = [(1 + 2 * n) * 2 ** n for n in range(9)]
print(iterate(8))
print(closed)
print("match:", iterate(8) == closed)
```

```text
[1, 6, 20, 56, 144, 352, 832, 1920, 4352]
[1, 6, 20, 56, 144, 352, 832, 1920, 4352]
match: True
```

## 3. Three roots (a cubic characteristic equation)

**Problem:** aₙ = 6aₙ₋₁ − 11aₙ₋₂ + 6aₙ₋₃, with a₀ = 2, a₁ = 5, a₂ = 15.

- Characteristic equation: r³ − 6r² + 11r − 6 = 0. Try small integers: r = 1 gives 1 − 6 + 11 − 6 = 0. Dividing out (r − 1) leaves r² − 5r + 6 = (r − 2)(r − 3). Roots: **1, 2, 3**.
- General solution: aₙ = A·1ⁿ + B·2ⁿ + C·3ⁿ = A + B·2ⁿ + C·3ⁿ.
- Initial values give three equations:
  - n = 0: A + B + C = 2
  - n = 1: A + 2B + 3C = 5
  - n = 2: A + 4B + 9C = 15
- Subtract the first from the second: B + 2C = 3. Subtract the second from the third: 2B + 6C = 10, so B + 3C = 5. Then C = 2, B = −1, A = 1.
- **aₙ = 1 − 2ⁿ + 2·3ⁿ.**

Python can solve the 3×3 system for us with exact fractions, so we can check the hand working too:

```python
from fractions import Fraction

def solve(m, rhs):                      # Gauss-Jordan elimination with exact fractions
    n = len(m)
    rows = [[Fraction(x) for x in row] + [Fraction(r)] for row, r in zip(m, rhs)]
    for col in range(n):
        pivot = next(r for r in range(col, n) if rows[r][col] != 0)
        rows[col], rows[pivot] = rows[pivot], rows[col]
        rows[col] = [x / rows[col][col] for x in rows[col]]
        for r in range(n):
            if r != col:
                rows[r] = [a - rows[r][col] * b for a, b in zip(rows[r], rows[col])]
    return [row[-1] for row in rows]

roots = [1, 2, 3]
initial = [2, 5, 15]
A, B, C = solve([[r ** n for r in roots] for n in range(3)], initial)
print("A, B, C =", A, B, C)

seq = initial[:]
for n in range(3, 10):
    seq.append(6 * seq[n - 1] - 11 * seq[n - 2] + 6 * seq[n - 3])
closed = [1 - 2 ** n + 2 * 3 ** n for n in range(10)]
print(seq)
print("match:", seq == closed)
```

```text
A, B, C = 1 -1 2
[2, 5, 15, 47, 147, 455, 1395, 4247, 12867, 38855]
match: True
```

## 4. Particular solutions: guess the shape of f(n)

For aₙ = c·aₙ₋₁ + f(n), guess a particular solution that **looks like f(n)**:

| f(n) | First guess for the particular solution |
|---|---|
| a constant k | a constant P |
| a polynomial in n of degree d | a polynomial of degree d |
| k·sⁿ (s is **not** a root) | P·sⁿ |
| k·sⁿ (s **is** a root of multiplicity m) | P·nᵐ·sⁿ (the "resonance" case) |

**Example A (s is not a root):** aₙ = 3aₙ₋₁ + 2ⁿ, a₀ = 1.

- Homogeneous part: r = 3, so A·3ⁿ.
- Guess P·2ⁿ: P·2ⁿ = 3P·2ⁿ⁻¹ + 2ⁿ. Divide by 2ⁿ⁻¹: 2P = 3P + 2, so P = −2.
- aₙ = A·3ⁿ − 2·2ⁿ = A·3ⁿ − 2ⁿ⁺¹. a₀ = 1 gives A − 2 = 1, so A = 3.
- **aₙ = 3ⁿ⁺¹ − 2ⁿ⁺¹.**

**Example B (resonance):** aₙ = 2aₙ₋₁ + 2ⁿ, a₀ = 1.

- Homogeneous part: A·2ⁿ. The extra term 2ⁿ has the **same base as the root**, so the guess P·2ⁿ fails (it gives P = P + 1, which is impossible).
- Guess P·n·2ⁿ instead: P·n·2ⁿ = 2·P(n − 1)·2ⁿ⁻¹ + 2ⁿ. Divide by 2ⁿ: Pn = P(n − 1) + 1, so P = 1.
- aₙ = (A + n)·2ⁿ. a₀ = 1 gives A = 1. **aₙ = (n + 1)·2ⁿ.**

**Example C (polynomial):** aₙ = aₙ₋₁ + n, a₀ = 0. The root is r = 1 and f(n) = n is a polynomial, which is also "1ⁿ times a polynomial", so resonance applies: the guess is one degree higher, Pn² + Qn. Solving gives **aₙ = n(n + 1)/2**, the sum 1 + 2 + … + n.

```python
def run(step, a0, n):
    a = [a0]
    for i in range(1, n + 1):
        a.append(step(a[i - 1], i))
    return a

N = 10
checks = {
    "A: a(n) = 3a(n-1) + 2^n": (run(lambda prev, n: 3 * prev + 2 ** n, 1, N), [3 ** (n + 1) - 2 ** (n + 1) for n in range(N + 1)]),
    "B: a(n) = 2a(n-1) + 2^n": (run(lambda prev, n: 2 * prev + 2 ** n, 1, N), [(n + 1) * 2 ** n for n in range(N + 1)]),
    "C: a(n) = a(n-1) + n":    (run(lambda prev, n: prev + n, 0, N), [n * (n + 1) // 2 for n in range(N + 1)]),
}
for name, (by_recurrence, by_formula) in checks.items():
    print(f"{name:26} first terms {by_recurrence[:6]}  formula ok: {by_recurrence == by_formula}")
```

```text
A: a(n) = 3a(n-1) + 2^n    first terms [1, 5, 19, 65, 211, 665]  formula ok: True
B: a(n) = 2a(n-1) + 2^n    first terms [1, 4, 12, 32, 80, 192]  formula ok: True
C: a(n) = a(n-1) + n       first terms [0, 1, 3, 6, 10, 15]  formula ok: True
```

## 5. Unrolling (the iteration method)

Some recurrences are easiest to solve by **substituting the recurrence into itself** until a pattern appears.

**T(n) = T(n − 1) + n, T(1) = 1** (for example, selection sort's comparisons):

T(n) = T(n − 1) + n = T(n − 2) + (n − 1) + n = … = T(1) + 2 + 3 + … + n = **n(n + 1)/2**, which is Θ(n²).

**T(n) = 2T(n/2) + n, T(1) = 1, n a power of 2** (merge sort):

- Level 0 does n work. Level 1 has 2 calls of size n/2: total n. Level 2 has 4 calls of size n/4: total n.
- There are log₂ n levels of this work, plus n leaves each costing T(1) = 1.
- **T(n) = n·log₂ n + n.**

![Recursion tree for T(n) = 2T(n/2) + n with n = 16: each level has twice as many calls of half the size, so every level costs 16; four levels of work plus 16 leaves give a total of 80](https://skills101.in/learn-img/discrete-math/unrolling-tree.svg)

```python
import math

def T(n):
    return 1 if n == 1 else 2 * T(n // 2) + n

for n in [2, 4, 8, 16, 1024]:
    print(n, T(n), n * int(math.log2(n)) + n)
```

```text
2 4 4
4 12 12
8 32 32
16 80 80
1024 11264 11264
```

The Master Theorem tells you only **Θ(n log n)**. Unrolling gives the **exact** count, which exam questions sometimes ask for.

## 6. Generating functions (a first look)

A **generating function** stores a whole sequence as the coefficients of a power series: G(x) = a₀ + a₁x + a₂x² + … . A recurrence becomes an algebra equation for G(x).

**Fibonacci:** Fₙ = Fₙ₋₁ + Fₙ₋₂, F₀ = 0, F₁ = 1. Multiply each term by xⁿ and add up:

G(x) − x = x·G(x) + x²·G(x), so **G(x) = x / (1 − x − x²)**.

To check this, divide the series: if G(x)·(1 − x − x²) = x, then comparing coefficients of xⁿ gives exactly the recurrence again. Python can do this "long division" of power series:

```python
def series_divide(num, den, terms):
    # coefficients of num(x) / den(x), assuming den[0] == 1
    out = []
    for n in range(terms):
        c = (num[n] if n < len(num) else 0) - sum(den[k] * out[n - k] for k in range(1, min(n, len(den) - 1) + 1))
        out.append(c)
    return out

print("x/(1-x-x^2):", series_divide([0, 1], [1, -1, -1], 12))
print("1/(1-2x)   :", series_divide([1], [1, -2], 8))
print("1/(1-x)^2  :", series_divide([1], [1, -2, 1], 8))
```

```text
x/(1-x-x^2): [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
1/(1-2x)   : [1, 2, 4, 8, 16, 32, 64, 128]
1/(1-x)^2  : [1, 2, 3, 4, 5, 6, 7, 8]
```

The first line is the Fibonacci sequence. The other two show two standard results: 1/(1 − 2x) generates 2ⁿ, and 1/(1 − x)² generates n + 1. Splitting a generating function into such simple fractions (partial fractions) is another way to reach the same closed forms as the characteristic equation.

## Common mistakes

- Writing A·rⁿ + B·rⁿ for a repeated root. Use (A + Bn)·rⁿ.
- Using the initial values **before** adding the particular solution. The constants must be found from the **full** solution.
- Missing the resonance case: if the guess makes the equation impossible (like P = P + 1), multiply the guess by n.
- Unrolling and forgetting the base-case term (the "+ n" from the leaves in merge sort).
- Not checking. Computing six terms both ways takes one minute and catches almost every slip.

## Quick recap

- Method: homogeneous solution + particular solution, then fit the initial values, then check.
- Repeated root r: (A + Bn)·rⁿ. Three roots: A·r₁ⁿ + B·r₂ⁿ + C·r₃ⁿ, solved as a 3×3 system.
- Particular solution looks like f(n); if f(n) = k·sⁿ and s is a root, multiply the guess by n.
- Unrolling gives exact answers: T(n) = T(n − 1) + n is n(n + 1)/2; merge sort's T(n) = n log₂ n + n.
- Generating functions turn a recurrence into an equation: Fibonacci's is x / (1 − x − x²).


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