Recurrence Relations

Introduction

A recurrence relation defines a sequence by expressing each term as a function of previous terms. Unlike explicit formulas that compute a_n directly, recurrences are iterative: to find a_n, we must first compute earlier terms.

Recurrence relations arise naturally in counting problems, algorithm analysis, dynamical systems, and financial mathematics. The Fibonacci sequence, binomial coefficients, and factorial all satisfy simple recurrences.

Solving a recurrence means finding an explicit (closed-form) formula for the n-th term. This transforms an iterative definition into a direct calculation, often revealing the growth rate and asymptotic behavior.

This page develops methods for solving recurrence relations, focusing on linear recurrences with constant coefficients and introducing generating function techniques.

Basic Definitions

Recurrence Relation

A recurrence relation for a sequence {(a_n)} is an equation that expresses (a_n) in terms of one or more previous terms (a_n−1),(a_n−2), and so on.

The order of a recurrence is the difference between the largest and smallest indices appearing. A first-order recurrence involves (a_n) and (a_n−1); a second-order involves (a_n),(a_n−1), and (a_n−2).

Initial Conditions

A recurrence alone does not determine a unique sequence. Initial conditions specify the first few terms, after which the recurrence determines all remaining terms.

A k-th order recurrence requires k initial conditions: typically (a_0),(a_1),…,(a_k−1).

Linear Recurrences

A linear recurrence has the form:

(a_n)=(c_1)*(a_n−1)+(c_2)*(a_n−2)+⋯+(c_k)*(a_n−k)+ƒ(n)

where the coefficients (c_i) are constants. If ƒ(n)=0, the recurrence is homogeneous; otherwise it is nonhomogeneous.

First-Order Linear Recurrences

Homogeneous Case

The simplest recurrence is (a_n)=r*(a_n−1) with initial condition (a_0). The solution is:

(a_n)=(a_0)*rn

This is geometric growth if |r|>1, decay if |r|<1, and constant if r=1.

Nonhomogeneous Case

For (a_n)=r*(a_n−1)+ƒ(n), the general solution combines the homogeneous solution with a particular solution:

(a_n)=(a_n)(h)+(a_n)(p)=C⋅rn+(a_n)(p)

Finding a particular solution depends on the form of ƒ(n). For ƒ(n)=d (a constant) with r≠1, try (a_n)(p)=A (a constant).

Substituting: A=r*A+d, so A=d/(1−r). The general solution is:

(a_n)=C*rn+d/(1−r).

Second-Order Linear Recurrences

The Characteristic Equation

For (a_n)=(c_1)*(a_n−1)+(c_2)*(a_n−2), assume a solution of the form (a_n)=rn. Substituting gives:

rn=(c_1)*r(n−1)+(c_2)*r(n−2)

Dividing by r(n−2) yields the characteristic equation:

r2−(c_1)*r−(c_2)=0

The roots of this quadratic determine the form of the general solution.

Distinct Real Roots

If the characteristic equation has distinct roots (r_1) and (r_2), the general solution is:

(a_n)=A*(r_1)n+B*(r_2)n

The constants A and B are determined by initial conditions (a_0) and (a_1).

Repeated Root

If the characteristic equation has a repeated root r, the general solution is:

(a_n)=(A+B*n)*rn

The factor n multiplying the second term handles the degeneracy when both roots coincide.

Complex Roots

Complex conjugate roots r=α±i*β lead to oscillatory solutions. Writing in polar form r=ρ*e(i*θ):

(a_n)=ρn*(A*cos(n*θ)+B*sin(n*θ))

The solution oscillates with period (2*π)/θ and amplitude growing or decaying as ρn.

The Fibonacci Sequence

The Fibonacci sequence satisfies (F_n)=(F_n−1)+(F_n−2) with (F_0)=0, (F_1)=1.

The characteristic equation r2−r−1=0 has roots:

ϕ=(1+√(,5))/2≈1.618,ϕ=(1−√(,5))/2≈−0.618

Applying initial conditions gives Binet's formula:

(F_n)=(ϕn−ϕn)/√(,5)

Since |ϕ|<1, the second term vanishes for large n, so (F_n) is asymptotic to (ϕn)/√(,5).

Higher-Order Recurrences

For a k-th order recurrence
(a_n)=(c_1)*(a_n−1)+⋯+(c_k)*(a_n−k), the characteristic equation is:

rk−(c_1)*r(k−1)−⋯−(c_k)=0

If all k roots are distinct, the general solution is a linear combination of powers:

(a_n)=(∑_i=1^k)((A_i))*(r_i)n

Repeated roots contribute terms with polynomial coefficients. A root r of multiplicity m contributes
rn,n*rn,…,n(m−1)*rn.

Nonhomogeneous Recurrences

For (a_n)=(c_1)*(a_n−1)+⋯+(c_k)*(a_n−k)+ƒ(n), the solution is:

(a_n)=(a_n)(h)+(a_n)(p)

where a(h) is the general solution to the homogeneous part and a(p) is any particular solution.

For ƒ(n) a polynomial, try a polynomial of the same degree (multiply by n if there is overlap with homogeneous solutions).

For ƒ(n)=bn, try A*bn (multiply by nm if b is a root of multiplicity m).

Applications

Algorithm Analysis

The running time T(n) of recursive algorithms satisfies a recurrence. For merge sort:
T(n)=2*T*(n/2)+O(n), giving T(n)=O*(n*(log_)(n)).

The Master theorem provides solutions for recurrences of the form
T(n)=a*T*(n/b)+ƒ(n), covering most divide-and-conquer algorithms.

Counting Problems

Many counting problems lead to recurrences. The number of ways to tile a 2×n board with dominoes satisfies (F_n) (Fibonacci). The Catalan numbers satisfy

(C_n)=(∑_k=0^n−1)((C_k))*(C_n−1−k).

Financial Mathematics

The balance (B_n) of a loan after n payments satisfies
(B_n)=(1+r)*(B_n−1)−P, where r is the interest rate and P is the payment. Solving this recurrence determines amortization schedules.

Dynamical Systems

Discrete dynamical systems evolve according to (x_n+1)=ƒ((x_n)). Linear systems have solutions given by powers of the iteration matrix. Nonlinear systems can exhibit chaos.

Generating Function Method

Generating functions offer an alternative approach to solving recurrences. Multiply the recurrence by xn and sum over n to get an equation for the generating function
G(x)=(∑_^)((a_n))*xn.

Solving for G(x) and expanding in partial fractions recovers the sequence coefficients. This method handles complex recurrences systematically.

Summary

A recurrence relation defines (a_n) in terms of previous terms. Together with initial conditions, it determines a unique sequence.

Linear recurrences with constant coefficients are solved using the characteristic equation. For
(a_n)=(c_1)*(a_n−1)+(c_2)*(a_n−2), solve r2−(c_1)*r−(c_2)=0.

Distinct roots (r_1),(r_2) give
(a_n)=A*(r_1)n+B*(r_2)n. Repeated roots give
(a_n)=(A+B*n)*rn. Complex roots produce oscillatory solutions.

The Fibonacci sequence has the closed form
(ϕn−ϕn)/√(,5), where ϕ is the golden ratio.

Nonhomogeneous recurrences add a particular solution to the homogeneous solution. The form of the particular solution depends on the forcing term ƒ(n).

Applications include algorithm analysis (running time), counting (combinatorics), finance (amortization), and dynamical systems.

Generating functions provide an alternative method by converting the recurrence into an algebraic equation.

The asymptotic behavior is dominated by the largest characteristic root. Understanding recurrences reveals the growth rates of sequences and algorithms.