Recurrence Relations and Difference Equations

A recurrence relation is an equation that recursively defines a sequence, where each term is a function of preceding terms. In mathematical analysis, these are the discrete analogues of differential equations. Studying recurrences allows us to find “closed-form” expressions—formulas that allow for the direct calculation of any term $a_n$ without manual iteration.

Classification of Recurrence Relations

1. Linear Recurrences: The terms appear only to the first power.
2. Homogeneous: The equation equals zero when all terms are moved to one side (no constant or separate function of $n$).
3. Order: The number of preceding terms the current term depends on. $a_n=3a_{n-1}+2a_{n-2}$ is a second-order linear homogeneous recurrence.

Solving Linear Homogeneous Recurrences

For a second-order linear homogeneous recurrence $a_n+c_1{a}_{n-1}+c_2{a}_{n-2}=0$, we assume a solution of the form $a_n=r^n$. Substituting this into the equation yields the Characteristic Equation: $r^2+c_{1}r+c_2=0$

Case 1: Two Distinct Real Roots ($r_1,r_2$)

The general solution is $a_n=A(r_1{)}^n+B(r_2{)}^n$. The coefficients $A$ and $B$ are determined by the initial conditions ($a_0,a_1$).

Case 2: One Repeated Real Root ($r$)

The general solution is $a_n=A(r{)}^n+Bn(r{)}^n$.

Case 3: Complex Roots

If the roots are $p\pm qi$, the solution involves trigonometric functions, reflecting the “oscillatory” nature of the sequence.

The Analytic Solution to Fibonacci

The Fibonacci sequence ($F_n=F_{n-1}+F_{n-2}$) has the characteristic equation $r^2-r-1=0$. Using the quadratic formula, the roots are: $\varphi =\frac{1+\sqrt{5}}{2}\text{and}\psi =\frac{1-\sqrt{5}}{2}$ Applying initial conditions $F_0=0,F_1=1$, we derive Binet’s Formula: $F_n=\frac{{\varphi }^n-{\psi }^n}{\sqrt{5}}$ This formula allows us to calculate the millionth Fibonacci number without ever calculating the previous 999,999.

Non-Homogeneous Recurrences

A non-homogeneous recurrence has the form $a_n=c_1{a}_{n-1}+\cdots +f(n)$. The general solution is $a_n=a_n^{(h)}+a_n^{(p)}$, where:

• $a_n^{(h)}$ is the solution to the homogeneous version.
• $a_n^{(p)}$ is a “particular” solution that satisfies the specific function $f(n)$.

This “Method of Undetermined Coefficients” is identical to the technique used in solving linear non-homogeneous differential equations.

Solving via Generating Functions

Generating functions provide a unified framework for solving recurrences. By defining $A(x)={\sum }_{n=0}^{\infty }{a}_n{x}^n$ and multiplying the recurrence relation by $x^n$, we can transform the recurrence into an algebraic equation for $A(x)$. Solving for $A(x)$ and performing a partial fraction decomposition allows us to extract the coefficients $a_n$.

Recurrences in Algorithm Analysis

In computer science, we encounter recurrences when analyzing Divide and Conquer algorithms.

• Merge Sort: $T(n)=2T(n/2)+n$.
• Binary Search: $T(n)=T(n/2)+1$.

These are solved using the Master Theorem, which provides asymptotic bounds ($O$ notation) based on the relationship between the branching factor, the reduction factor, and the “extra” work done per step.

Discrete vs. Continuous Dynamics

A recurrence relation $a_n=f(a_{n-1})$ is a Discrete Dynamical System. While linear recurrences are well-behaved, non-linear recurrences (like the Logistic Map $x_{n+1}=r{x}_n(1-x_n)$) can exhibit chaotic behavior once the parameters exceed certain thresholds. This illustrates how simple recursive rules can lead to immense complexity.

Computational Methods: Dynamic Programming

While closed-form solutions are elegant, they are often computationally expensive due to floating-point precision (e.g., in Binet’s formula). In practice, we use Linear Recurrence Solvers or Matrix Exponentiation.

/**
 * Solving Fibonacci in O(log n) time using Matrix Exponentiation.
 * The transformation matrix is [[1, 1], [1, 0]].
 */
type Matrix2x2 = [[number, number], [number, number]];

function multiply(A: Matrix2x2, B: Matrix2x2): Matrix2x2 {
    return [
        [A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]],
        [A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]]
    ];
}

function power(A: Matrix2x2, n: number): Matrix2x2 {
    if (n === 1) return A;
    const half = power(A, Math.floor(n / 2));
    const squared = multiply(half, half);
    return n % 2 === 0 ? squared : multiply(squared, A);
}

const nthFib = (n: number) => n === 0 ? 0 : power([[1, 1], [1, 0]], n)[0][1];

Knowledge Check

By mastering recurrence relations, we gain the ability to predict the long-term behavior of systems that evolve in discrete steps, from the growth of populations to the execution time of complex algorithms.