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 is an equation that expresses in terms of one or more previous terms , and so on.
The order of a recurrence is the difference between the largest and smallest indices appearing. A first-order recurrence involves and ; a second-order involves , and .
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 -th order recurrence requires initial conditions: typically .
Linear Recurrences
A linear recurrence has the form:
where the coefficients are constants. If , the recurrence is homogeneous; otherwise it is nonhomogeneous.
First-Order Linear Recurrences
Homogeneous Case
The simplest recurrence is with initial condition . The solution is:
This is geometric growth if , decay if , and constant if .
Nonhomogeneous Case
For , the general solution combines the homogeneous solution with a particular solution:
Finding a particular solution depends on the form of . For (a constant) with , try (a constant).
Substituting: , so . The general solution is:
.
Second-Order Linear Recurrences
The Characteristic Equation
For , assume a solution of the form . Substituting gives:
Dividing by yields the characteristic equation:
The roots of this quadratic determine the form of the general solution.
Distinct Real Roots
If the characteristic equation has distinct roots and , the general solution is:
The constants and are determined by initial conditions and .
Repeated Root
If the characteristic equation has a repeated root , the general solution is:
The factor multiplying the second term handles the degeneracy when both roots coincide.
Complex Roots
Complex conjugate roots lead to oscillatory solutions. Writing in polar form :
The solution oscillates with period and amplitude growing or decaying as .
The Fibonacci Sequence
The Fibonacci sequence satisfies with , .
The characteristic equation has roots:
Applying initial conditions gives Binet's formula:
Since , the second term vanishes for large , so is asymptotic to .
Higher-Order Recurrences
For a -th order recurrence
, the characteristic equation is:
If all roots are distinct, the general solution is a linear combination of powers:
Repeated roots contribute terms with polynomial coefficients. A root of multiplicity contributes
.
Nonhomogeneous Recurrences
For , the solution is:
where is the general solution to the homogeneous part and is any particular solution.
For a polynomial, try a polynomial of the same degree (multiply by if there is overlap with homogeneous solutions).
For , try (multiply by if is a root of multiplicity ).
Applications
Algorithm Analysis
The running time of recursive algorithms satisfies a recurrence. For merge sort:
, giving .
The Master theorem provides solutions for recurrences of the form
, covering most divide-and-conquer algorithms.
Counting Problems
Many counting problems lead to recurrences. The number of ways to tile a board with dominoes satisfies (Fibonacci). The Catalan numbers satisfy
.
Financial Mathematics
The balance of a loan after payments satisfies
, where is the interest rate and is the payment. Solving this recurrence determines amortization schedules.
Dynamical Systems
Discrete dynamical systems evolve according to . 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 and sum over to get an equation for the generating function
.
Solving for and expanding in partial fractions recovers the sequence coefficients. This method handles complex recurrences systematically.
Summary
A recurrence relation defines 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
, solve .
Distinct roots give
. Repeated roots give
. Complex roots produce oscillatory solutions.
The Fibonacci sequence has the closed form
, 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 .
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.