Difficulty: Intermediate | Prerequisites: Basic algebra, summation notation, geometric series formula

TL;DR

A recurrence relation defines a sequence by expressing each term as a function of earlier terms. To find a closed-form (non-recursive) formula, you apply backwards substitution: repeatedly expand the recurrence until a pattern emerges, then simplify using known summation identities. You can verify the closed form with a proof by induction.

Key Terms

Recurrence relation

A formula that defines each term of a sequence using one or more previous terms, plus a base case. Think of it as a recipe that says "to get the next value, do this to the ones you already have."

Closed-form solution

An explicit formula for the nth term of a sequence that requires no recursion, only direct computation. In simple terms, it is the non-recursive version of the same sequence.

Backwards substitution (aka repeated substitution, unrolling)

A technique for solving recurrences: you repeatedly substitute the recurrence into itself, expanding until you spot a summation pattern you can simplify. Think of it as peeling back the layers of recursion one step at a time.

Geometric series formula

The identity used to collapse sums of the form 1 + r + r^2 + ... + r^(n-1) = (r^n - 1) / (r - 1). This is the workhorse formula that lets you simplify the sum that appears after unrolling a recurrence with a constant multiplier.

Base case (of a recurrence)

The explicitly given value(s) that anchor the sequence and stop the recursion. Without a base case, backwards substitution has no stopping point.

Core Content

Solving a recurrence by backwards substitution

The general method has three steps:

• Expand the recurrence repeatedly, substituting T(n-1), T(n-2), etc., each time

• Identify the resulting summation pattern and simplify it (often using the geometric series formula)

• Verify the closed form by checking the base case and proving the inductive step

Worked example 1: T(n) = 3T(n-1) - 2, T(0) = 5

Start by expanding:

• T(n) = 3T(n-1) - 2

• = 3(3T(n-2) - 2) - 2 = 3^2 T(n-2) - 3 * 2 - 2

• = 3^2(3T(n-3) - 2) - 3 * 2 - 2 = 3^3 T(n-3) - 3^2 * 2 - 3 * 2 - 2

After n steps, the pattern becomes:

• T(n) = 3^n * T(0) - 2 * (3^(n-1) + 3^(n-2) + ... + 3 + 1)

• = 3^n * 5 - 2 * sum from i=0 to n-1 of 3^i

Apply the geometric series formula, sum = (3^n - 1) / (3 - 1) = (3^n - 1) / 2:

• T(n) = 5 * 3^n - 2 * (3^n - 1) / 2

• = 5 * 3^n - (3^n - 1)

• = 4 * 3^n + 1

Verify: T(0) = 4 * 1 + 1 = 5. Correct.

Worked example 2: recproc(n, x), base case recproc(1) = 0

Given the recursive procedure:

• If n = 1, return 0

• Otherwise, return recproc(n-1, x) + x

Let R(n) = recproc(n, x). Expand:

• R(n) = R(n-1) + x

• = R(n-2) + 2x

• = R(n-3) + 3x

• ...

• = R(1) + (n-1)x

• = 0 + (n-1)x

• = (n-1)x

This is a straightforward linear recurrence. Each recursive call adds x once, and there are n-1 calls before the base case.

Worked example 3: converting a recursive procedure to a recurrence

Given:

• If n < 2, return n + 2

• Otherwise, return recproc(n-1) + recproc(n-2)

The base cases give a_0 = 0 + 2 = 2 and a_1 = 1 + 2 = 3. The recursive case is a_n = a_(n-1) + a_(n-2) for n >= 2. This is a Fibonacci-like recurrence with shifted initial values.

Formulas

Geometric series (finite):

\sum_{i=0}^{n-1} r^i = \frac{r^n - 1}{r - 1}, \quad r \neq 1

Closed form for T(n) = 3T(n-1) - 2, T(0) = 5:

T(n) = 4 \cdot 3^n + 1

Closed form for recproc(n, x), recproc(1) = 0:

R(n) = (n - 1)x

Recurrence-to-sequence conversion, recproc(n), a_0 = 2, a_1 = 3:

a_n = a_{n-1} + a_{n-2}, \quad n \geq 2

Real-World Applications

Recurrence relations model any process where the next state depends on previous states: population growth models in biology, compound interest in finance, and the running time of recursive algorithms in computer science. Backwards substitution is the same technique used to derive the time complexity of divide-and-conquer algorithms such as merge sort and binary search.

Common Misconceptions

• Students often forget to apply the geometric series formula and instead try to manually sum the expanded terms. The formula exists precisely for this step.

• Students sometimes confuse the base case value with the closed-form constant. In example 1, T(0) = 5 is the base case, but the closed form is 4 * 3^n + 1, not 5 * 3^n.

• When converting a recursive procedure to a recurrence, students sometimes write the wrong base case values by misreading what the function returns for small inputs. Always trace through the code for n = 0, n = 1 by hand.

• Students occasionally apply the geometric series formula with the wrong bounds or forget to account for the index offset in the summation.

Why It Matters / Exam Flags

• ⚠️ Backwards substitution is a very commonly tested technique. Expect to be given a recurrence and asked to find the closed form.

• ⚠️ You will likely need to verify your closed form using induction (see the companion notes on induction).

• ⚠️ Know the geometric series formula cold. It appears in nearly every recurrence problem that has a constant multiplier.

• ⚠️ Be prepared to read a recursive procedure and extract both the recurrence relation and the base case values from the code.

Quick Self-Test

1. True or False: The closed form of T(n) = 3T(n-1) - 2, T(0) = 5 is 5 * 3^n. (False, it is 4 * 3^n + 1.)

1. Fill in the blank: The geometric series sum 1 + 3 + 9 + ... + 3^(n-1) equals ______. ((3^n - 1) / 2.)

1. True or False: recproc(n, x) with base case recproc(1) = 0 computes nx. (False, it computes (n-1)x.)

1. Fill in the blank: To convert a recursive procedure into a recurrence, you need the ______ and the ______. (Base case(s) and the recursive case.)

1. True or False: After finding a closed form by backwards substitution, you should verify it by induction. (True.)

Practice Q&A

Q: Given T(n) = 2T(n-1) + 1, T(0) = 0, find the closed form using backwards substitution.

A: Expand: T(n) = 2T(n-1) + 1 = 2(2T(n-2) + 1) + 1 = 2^2 T(n-2) + 2 + 1. After n steps: T(n) = 2^n * T(0) + (2^(n-1) + ... + 2 + 1) = 0 + 2^n - 1 = 2^n - 1.

Q: A recursive function returns 3 when n = 0, and returns f(n-1) + 4 otherwise. What is the closed form?

A: f(n) = 3 + 4n. Each call adds 4, and there are n calls before the base case, which contributes 3.

Q: Why does solving T(n) = 3T(n-1) - 2 produce a geometric series in the expansion?

A: Because the multiplier 3 is applied at each recursive step, so after k expansions the constant term -2 has been scaled by 3^0, 3^1, ..., 3^(k-1), forming a geometric series with ratio 3.

Q: Given recproc(n) where recproc(n) returns recproc(n-1) + recproc(n-2) for n >= 2, with recproc(0) = 2, recproc(1) = 3, what is a_4?

A: a_2 = 3 + 2 = 5, a_3 = 5 + 3 = 8, a_4 = 8 + 5 = 13.

Connections to Other Topics

This connects directly to mathematical induction, because the standard workflow is: find the closed form by backwards substitution, then prove it correct by induction. It also connects to algorithm analysis, where the running time of recursive algorithms (merge sort, binary search) is expressed as a recurrence and solved the same way. The Fibonacci-like recurrence in example 3 ties to strong induction, since proving properties of two-term recurrences requires assuming the result holds for multiple previous values.

Related Terms / Search Tags

Recurrence relation, closed form, closed-form solution, backwards substitution, repeated substitution, unrolling a recurrence, geometric series, geometric sum formula, recursive formula to explicit formula, solving recurrences, CS182, foundations of computer science, Purdue CS182, recproc, T(n), base case, recursive procedure, Fibonacci-like recurrence