Mathematics.

sequences and recursion

Recurrence Relations

Discrete Mathematics30 minDifficulty5 out of 10

You should know: sequences and series

Overview

A recurrence relation is an equation that defines each term of a sequence as a combination of previous terms. If only k previous terms appear in the equation, k is called the order of the relation. Given the first k values of the sequence (the initial conditions), every later term is determined by repeatedly applying the equation. The Fibonacci recurrence Fₙ = Fₙ₋₁ + Fₙ₋₂ and the factorial recurrence n! = n·(n-1)! are the two most famous examples: one is order 2, the other order 1.

Intuition

A recurrence relation is a recipe, not a lookup table: it tells you how to build the next term out of the ones you already have, the way each rung of a ladder is built by standing on the rung below it. Knowing the recipe alone isn't enough — you also need to know where the ladder starts (the initial conditions), because the same recipe (say, 'add the previous two terms') produces wildly different sequences depending on the starting values. Solving a recurrence means finding a 'closed form' — a direct formula for the nth term that doesn't require computing all the earlier ones first.

Formal Definition

Definition

A first-order recurrence expresses term n in terms of term n-1 alone; a k-th order (linear) recurrence expresses term n as a fixed linear combination of the k preceding terms.

un=φ(n,un−1)for n>0u_n = \varphi(n, u_{n-1}) \quad \text{for } n > 0
First-order recurrence
un=φ(n,un−1,un−2,…,un−k)for n≥ku_n = \varphi(n, u_{n-1}, u_{n-2}, \ldots, u_{n-k}) \quad \text{for } n \ge k
Order-k recurrence
un=c1un−1+c2un−2+⋯+ckun−ku_n = c_1 u_{n-1} + c_2 u_{n-2} + \cdots + c_k u_{n-k}
Linear homogeneous, constant coefficients
Fn=Fn−1+Fn−2,F0=0, F1=1F_n = F_{n-1} + F_{n-2}, \quad F_0 = 0,\ F_1 = 1
Fibonacci recurrence

Notation

NotationMeaning
unu_nThe nth term of the sequence, defined recursively
kkNumber of preceding terms the recurrence depends on
xk=c1xk−1+⋯+ckx^k = c_1 x^{k-1} + \cdots + c_kPolynomial whose roots give the closed-form solution

Derivation

To solve a linear homogeneous recurrence with constant coefficients, guess a solution of the form uₙ = xⁿ (x ≠ 0) and substitute into the recurrence. This turns the recurrence into a polynomial equation in x — the characteristic equation. For the second-order case uₙ = c₁uₙ₋₁ + c₂uₙ₋₂:

xn=c1xn−1+c2xn−2x^n = c_1 x^{n-1} + c_2 x^{n-2}

Substitute the trial solution uₙ = xⁿ

x2−c1x−c2=0x^2 - c_1 x - c_2 = 0

Divide by x^{n-2} to get the characteristic equation

un=Ax1n+Bx2n(x1≠x2)u_n = A x_1^n + B x_2^n \quad (x_1 \ne x_2)

Distinct roots: general solution is a linear combination of the two geometric sequences

un=(A+Bn)x1n(x1=x2)u_n = (A + Bn) x_1^n \quad (x_1 = x_2)

Repeated root: multiply the second solution by n

A,B determined by the initial conditions u0,u1A, B \text{ determined by the initial conditions } u_0, u_1

Two initial values pin down the two constants

Applications

The running time of divide-and-conquer algorithms (e.g. merge sort, T(n) = 2T(n/2) + n) is expressed and solved as a recurrence relation.

Worked Examples

  1. Write the characteristic equation from the trial solution Fₙ = xⁿ.

    x2−x−1=0x^2 - x - 1 = 0

  2. Solve the quadratic for the two distinct roots (the golden ratio and its conjugate).

    x=1±52  ⟹  x1=φ=1+52, x2=ψ=1−52x = \frac{1 \pm \sqrt{5}}{2} \implies x_1 = \varphi = \frac{1+\sqrt5}{2},\ x_2 = \psi = \frac{1-\sqrt5}{2}

  3. General solution is a combination of the two geometric sequences.

    Fn=Aφn+BψnF_n = A\varphi^n + B\psi^n

  4. Apply F₀ = 0 and F₁ = 1 to solve for A and B, giving Binet's formula.

    Fn=φn−ψn5F_n = \frac{\varphi^n - \psi^n}{\sqrt5}

Answer: Fₙ = (φⁿ - ψⁿ)/√5, where φ = (1+√5)/2 and ψ = (1-√5)/2 (Binet's formula).

Practice Problems

Difficulty 5/10

Solve uₙ = 5uₙ₋₁ - 6uₙ₋₂ with u₀ = 2, u₁ = 5.

Difficulty 6/10

Find the order of the recurrence n! = n·(n-1)! and explain why one initial condition suffices to determine the whole sequence.

Common Mistakes

Common Mistake

Writing the general solution as uₙ = Axₙ + Bxₙ (using the same root twice) when the characteristic equation has a repeated root.

A repeated root x₁ = x₂ only gives one independent solution x₁ⁿ; the second independent solution is n·x₁ⁿ, so the general solution is (A + Bn)x₁ⁿ.

Common Mistake

Forgetting that the number of initial conditions must match the order of the recurrence.

An order-k recurrence has a k-dimensional family of solutions (k arbitrary constants), so exactly k initial values are needed to pin down a unique sequence.

Summary

  • A recurrence relation defines each term from previous terms; the order k is how many prior terms it references.
  • Initial conditions (k of them, for order k) select one specific sequence out of the whole solution family.
  • Linear recurrences with constant coefficients are solved via a characteristic polynomial in x, found by substituting uₙ = xⁿ.
  • Distinct roots give a sum of geometric terms; a repeated root x₁ requires the extra factor n, i.e. (A+Bn)x₁ⁿ.
  • Recurrences model Fibonacci numbers, factorials, compound interest, and the running time of recursive algorithms.

References

  1. WebsiteWikipedia — Recurrence relation
  2. BookRosen, K. Discrete Mathematics and Its Applications, 8th ed., Ch. 8.