Home / Courses / Discrete Mathematics / Unit 6

Discrete Mathematics Unit 6: Recurrence relations

A recurrence defines each term from earlier ones. Solving it gives a closed formula.

Covers: Setting up recurrences, solving linear recurrences, generating functions (intro)

Study guide

A recurrence relation defines each term of a sequence from earlier terms, like the Fibonacci recurrence Fₙ = Fₙ₋₁ + Fₙ₋₂ with initial conditions F₀ = 0, F₁ = 1. Setting up a recurrence means finding how a problem of size n depends on smaller sizes: counting bit strings without two consecutive 0s, the Tower of Hanoi (Hₙ = 2Hₙ₋₁ + 1), or compound interest. Initial conditions are needed to pin down the sequence.

A linear homogeneous recurrence with constant coefficients, like aₙ = c₁aₙ₋₁ + c₂aₙ₋₂, is solved with its characteristic equation r² = c₁r + c₂. If the roots r₁ and r₂ are distinct, the general solution is aₙ = A·r₁ⁿ + B·r₂ⁿ. If there's a repeated root r, it's aₙ = (A + Bn)rⁿ. Use the initial terms to solve for A and B. For example, aₙ = 5aₙ₋₁ − 6aₙ₋₂ has roots 2 and 3, so aₙ = A·2ⁿ + B·3ⁿ.

Nonhomogeneous recurrences add a function of n, like aₙ = 2aₙ₋₁ + 1. Their solutions are the homogeneous solution plus a particular solution guessed in the form of the extra term, similar to differential equations.

Generating functions encode a sequence as the coefficients of a power series, G(x) = Σ aₙxⁿ. Recurrences become algebraic equations for G(x), and counting problems become products of series. For instance, 1/(1 − x) generates the all-ones sequence.

When several quantities depend on one another, write one recurrence for each, then add or substitute them to get a single recurrence. For example, a total that satisfies Tₙ = 2Tₙ₋₁ gives Tₙ = 2ⁿT₀. A probability can satisfy a recurrence too. Condition on the first or last step (by the law of total probability), so pₙ is a weighted average of earlier values. Then state enough initial values to determine the sequence.

Key ideas

• Set up a recurrence by expressing the nth case in terms of smaller cases.
• Linear homogeneous recurrence aₙ = c₁aₙ₋₁ + c₂aₙ₋₂: solve r² = c₁r + c₂.
• Distinct roots: aₙ = A·r₁ⁿ + B·r₂ⁿ. Repeated root: aₙ = (A + Bn)rⁿ.
• Use initial terms to find the constants.
• Generating functions encode a sequence as a power series.

Formulas and rules

Common mistakes

• Forgetting the n factor with a repeated root.
• Using the wrong number of initial conditions.

Words to know

Characteristic equation (recurrence)

For aₙ = c₁aₙ₋₁ + c₂aₙ₋₂, solve r² = c₁r + c₂.

General solution with distinct roots r₁, r₂

aₙ = A·r₁ⁿ + B·r₂ⁿ

General solution with a repeated root r

aₙ = (A + Bn)rⁿ

Fibonacci recurrence

Fₙ = Fₙ₋₁ + Fₙ₋₂

Constants in a recurrence solution

Found from the initial terms of the sequence.

Recurrence relation

Defines each term from earlier terms.

Initial conditions

The starting terms that pin down a sequence.

Tower of Hanoi recurrence

Hₙ = 2Hₙ₋₁ + 1

Linear homogeneous recurrence

aₙ = c₁aₙ₋₁ + … + cₖaₙ₋ₖ

Nonhomogeneous recurrence

A linear recurrence plus a function of n.

Generating function

G(x) = Σ aₙxⁿ

Sample practice questions

21 more questions like these, from level 1 to 5, are in the practice set.