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 {an} the set a sub n is an equation that expresses an a sub n in terms of one or more previous terms an−1,an−2 a sub n minus 1 comma a sub n minus 2, and so on.

The order of a recurrence is the difference between the largest and smallest indices appearing. A first-order recurrence involves an a sub n and an−1 a sub n minus 1; a second-order involves an,an−1 a sub n comma a sub n minus 1, and an−2 a sub n minus 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 k-th order recurrence requires k k initial conditions: typically a0,a1,…,ak−1 a sub 0 comma a sub 1 comma dot dot dot comma a sub k minus 1.

Linear Recurrences

A linear recurrence has the form:

an=c1⁢an−1+c2⁢an−2+⋯+ck⁢an−k+ƒ⁡(n) a sub n equals c sub 1 a sub n minus 1 plus c sub 2 a sub n minus 2 plus dot dot dot plus c sub k a sub n minus k plus f with hook of n

where the coefficients ci c sub i are constants. If ƒ⁡(n)=0 f with hook of n equals 0, the recurrence is homogeneous; otherwise it is nonhomogeneous.

First-Order Linear Recurrences

Homogeneous Case

The simplest recurrence is an=r⁢an−1 a sub n equals r a sub n minus 1 with initial condition a0 a sub 0. The solution is:

an=a0⁢rn a sub n equals a sub 0 r to the n-th power

This is geometric growth if |r|>1 the absolute value of r is greater than 1, decay if |r|<1 the absolute value of r is less than 1, and constant if r=1 r equals 1.

Nonhomogeneous Case

For an=r⁢an−1+ƒ⁡(n) a sub n equals r a sub n minus 1 plus f with hook of n, the general solution combines the homogeneous solution with a particular solution:

an=an(h)+an(p)=C⋅rn+an(p) a sub n equals a sub n raised to the open paren h close paren power plus a sub n raised to the p power equals C times r to the n-th power plus a sub n raised to the p power

Finding a particular solution depends on the form of ƒ⁡(n) f with hook of n. For ƒ⁡(n)=d f with hook of n equals d (a constant) with r≠1 r is not equal to 1, try an(p)=A a sub n raised to the p power equals A (a constant).

Substituting: A=r⁢A+d A equals r A plus d, so A=d1−r A equals the fraction with numerator d and denominator 1 minus r. The general solution is:

an=C⁢rn+d1−r a sub n equals C r to the n-th power plus the fraction with numerator d and denominator 1 minus r.

Second-Order Linear Recurrences

The Characteristic Equation

For an=c1⁢an−1+c2⁢an−2 a sub n equals c sub 1 a sub n minus 1 plus c sub 2 a sub n minus 2, assume a solution of the form an=rn a sub n equals r to the n-th power. Substituting gives:

rn=c1⁢rn−1+c2⁢rn−2 r to the n-th power equals c sub 1 r raised to the n minus 1 power plus c sub 2 r raised to the n minus 2 power

Dividing by rn−2 r raised to the n minus 2 power yields the characteristic equation:

r2−c1⁢r−c2=0 r squared minus c sub 1 r minus c sub 2 equals 0

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

Distinct Real Roots

If the characteristic equation has distinct roots r1 r sub 1 and r2 r sub 2, the general solution is:

an=A⁢r1n+B⁢r2n a sub n equals A r sub 1 to the n-th power plus B r sub 2 to the n-th power

The constants A A and B B are determined by initial conditions a0 a sub 0 and a1 a sub 1.

Repeated Root

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

an=(A+B⁢n)⁢rn a sub n equals open paren A plus B n close paren times r to the n-th power

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

Complex Roots

Complex conjugate roots r=α±i⁢β r equals alpha plus or minus i beta lead to oscillatory solutions. Writing in polar form r=ρ⁢ei⁢θ r equals rho e raised to the i theta power:

an=ρn⁢(A⁢cos⁡n⁢θ+B⁢sin⁡n⁢θ) a sub n equals rho to the n-th power times open paren A cosine n theta plus B sine n theta close paren

The solution oscillates with period 2⁢πθ 2 pi over theta and amplitude growing or decaying as ρn rho to the n-th power.

The Fibonacci Sequence

The Fibonacci sequence satisfies Fn=Fn−1+Fn−2 F sub n equals F sub n minus 1 plus F sub n minus 2 with F0=0 F sub 0 equals 0, F1=1 F sub 1 equals 1.

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

ϕ=1+52≈1.618,ϕ^=1−52≈−0.618 phi equals the fraction with numerator 1 plus the square root of 5 and denominator 2 almost equals 1.618 comma phi hat equals the fraction with numerator 1 minus the square root of 5 and denominator 2 almost equals negative 0.618

Applying initial conditions gives Binet's formula:

Fn=ϕn−ϕ^n5 F sub n equals the fraction with numerator phi to the n-th power minus phi hat to the n-th power and denominator the square root of 5

Since |ϕ^|<1 the absolute value of phi hat is less than 1, the second term vanishes for large n n, so Fn F sub n is asymptotic to ϕn5 the fraction with numerator phi to the n-th power and denominator the square root of 5.

Higher-Order Recurrences

For a k k-th order recurrence
an=c1⁢an−1+⋯+ck⁢an−k a sub n equals c sub 1 a sub n minus 1 plus dot dot dot plus c sub k a sub n minus k, the characteristic equation is:

rk−c1⁢rk−1−⋯−ck=0 r to the k-th power minus c sub 1 r raised to the k minus 1 power minus dot dot dot minus c sub k equals 0

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

an=∑i=1k(Ai)⁢rin a sub n equals the sum from i equals 1 to k of open paren A sub i close paren r sub i to the n-th power

Repeated roots contribute terms with polynomial coefficients. A root r r of multiplicity m m contributes
rn,n⁢rn,…,nm−1⁢rn r to the n-th power comma n r to the n-th power comma dot dot dot comma n raised to the m minus 1 power r to the n-th power.

Nonhomogeneous Recurrences

For an=c1⁢an−1+⋯+ck⁢an−k+ƒ⁡(n) a sub n equals c sub 1 a sub n minus 1 plus dot dot dot plus c sub k a sub n minus k plus f with hook of n, the solution is:

an=an(h)+an(p) a sub n equals a sub n raised to the open paren h close paren power plus a sub n raised to the p power

where a(h) a raised to the open paren h close paren power is the general solution to the homogeneous part and a(p) a raised to the p power is any particular solution.

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

For ƒ⁡(n)=bn f with hook of n equals b to the n-th power, try A⁢bn A b to the n-th power (multiply by nm n to the m-th power if b b is a root of multiplicity m m).

Applications

Algorithm Analysis

The running time T⁡(n) T of n of recursive algorithms satisfies a recurrence. For merge sort:
T⁡(n)=2⁢T⁢(n/2)+O⁡(n) T of n equals 2 T times open paren n divided by 2 close paren plus O of n, giving T⁡(n)=O⁢(n⁢log⁡n) T of n equals O times open paren n log n close paren.

The Master theorem provides solutions for recurrences of the form
T⁡(n)=a⁢T⁢(n/b)+ƒ⁡(n) T of n equals a T times open paren n divided by b close paren plus f with hook of n, covering most divide-and-conquer algorithms.

Counting Problems

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

Cn=∑k=0n−1(Ck)⁢Cn−1−k C sub n equals the sum from k equals 0 to n minus 1 of open paren C sub k close paren C sub n minus 1 minus k.

Financial Mathematics

The balance Bn B sub n of a loan after n n payments satisfies
Bn=(1+r)⁢Bn−1−P B sub n equals open paren 1 plus r close paren times B sub n minus 1 minus P, where r r is the interest rate and P P is the payment. Solving this recurrence determines amortization schedules.

Dynamical Systems

Discrete dynamical systems evolve according to xn+1=ƒ⁡(xn) x sub n plus 1 equals f with hook of open paren x sub n close paren. 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 x to the n-th power and sum over n n to get an equation for the generating function
G⁡(x)=∑(an)⁢xn G of x equals the sum of open paren a sub n close paren x to the n-th power.

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

Summary

A recurrence relation defines an a sub 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
an=c1⁢an−1+c2⁢an−2 a sub n equals c sub 1 a sub n minus 1 plus c sub 2 a sub n minus 2, solve r2−c1⁢r−c2=0 r squared minus c sub 1 r minus c sub 2 equals 0.

Distinct roots r1,r2 r sub 1 comma r sub 2 give
an=A⁢r1n+B⁢r2n a sub n equals A r sub 1 to the n-th power plus B r sub 2 to the n-th power. Repeated roots give
an=(A+B⁢n)⁢rn a sub n equals open paren A plus B n close paren times r to the n-th power. Complex roots produce oscillatory solutions.

The Fibonacci sequence has the closed form
ϕn−ϕ^n5 the fraction with numerator phi to the n-th power minus phi hat to the n-th power and denominator the square root of 5, where ϕ phi 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) f with hook of 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.