Skills101

AdvancedDiscrete Mathematics · Lesson 9 of 10 · Updated ·

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

The earlier lesson on 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

  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ⁿ.
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)
[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:

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)
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 ka constant P
a polynomial in n of degree da 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.

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}")
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

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)
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:

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))
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 what you learned

📝 Quiz: Solving Recurrences5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →