Recurrence Relation · aiwiki.page

A recurrence relation is an equation that relates terms of a sequence to other terms of the same sequence, usually at smaller indices. Together with suitable initial conditions, it can define a sequence by successive computation. Recurrence relations express recursion mathematically and are used to describe numerical patterns and analyze algorithms. Solving a recurrence generally means finding an explicit formula or determining how its solutions grow. (discrete.openmathbooks.org)

Definition and initial conditions

A common finite-order form is

a_n=F(n,a_{n-1},a_{n-2},\ldots,a_{n-k}), \qquad n\ge k,

where $F$ is a specified function and $k$ is a fixed positive integer. When $F$ genuinely depends on the term $k$ steps earlier, the recurrence has order $k$ . For this explicit form, specifying $a_0,\ldots,a_{k-1}$ determines subsequent terms uniquely, provided every evaluation of $F$ is defined. A recurrence without initial conditions normally describes a family of sequences rather than one sequence. (ocw.mit.edu)

For example,

a_n=a_{n-1}+d,\qquad a_0=A

gives $a_n=A+nd$ . Likewise, $a_n=ra_{n-1}$ gives $a_n=Ar^n$ . These illustrate the distinction between a recursive specification, which refers to previous values, and a closed-form expression, which computes a term directly from its index. A proposed formula can be verified using mathematical induction: check the initial values, then show that the formula satisfies the recurrence. (discrete.openmathbooks.org)

Classification

A recurrence is linear when its sequence terms occur to the first power and are not multiplied together. A linear recurrence of order $k$ can be written

a_n=c_1(n)a_{n-1}+\cdots+c_k(n)a_{n-k}+g(n).

It has constant coefficients when the $c_j(n)$ are independent of $n$ . It is homogeneous when $g(n)=0$ , and nonhomogeneous otherwise. For a homogeneous linear recurrence, any linear combination of solutions is again a solution. For a nonhomogeneous recurrence, the general solution is a particular solution plus the general solution of the corresponding homogeneous relation. (ocw.mit.edu)

Variable coefficients need not make a recurrence nonlinear. For instance, factorials satisfy $a_n=na_{n-1}$ , with $a_0=1$ , which is linear but has a coefficient depending on $n$ . By contrast, an expression involving $a_{n-1}^2$ is nonlinear. Thus linearity, coefficient dependence, and homogeneity are separate classification criteria. (ocw.mit.edu)

Characteristic-root method

For a homogeneous linear recurrence with constant coefficients,

a_n=c_1a_{n-1}+\cdots+c_ka_{n-k},

substitution of an exponential trial solution $a_n=r^n$ leads to the characteristic polynomial

p(r)=r^k-c_1r^{k-1}-\cdots-c_k.

Assuming $c_k\ne0$ , if its roots $r_1,\ldots,r_k$ are distinct, the general solution is

a_n=C_1r_1^n+\cdots+C_kr_k^n.

The constants are determined from the initial conditions through a system of linear equations. A root $r$ of multiplicity $m$ instead contributes

(C_0+C_1n+\cdots+C_{m-1}n^{m-1})r^n.

The method also accommodates complex roots. (math.libretexts.org)

The Fibonacci sequence is the standard second-order example:

F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}.

Its characteristic equation is $r^2-r-1=0$ . Writing $\phi=(1+\sqrt5)/2$ and $\psi=(1-\sqrt5)/2$ , the initial conditions yield

F_n=\frac{\phi^n-\psi^n}{\sqrt5}.

Although this formula contains irrational quantities, it gives integer values at nonnegative integer indices because it satisfies the defining recurrence and initial conditions. (math.libretexts.org)

Generating functions

An ordinary generating function packages a sequence into a power series:

A(x)=\sum_{n=0}^{\infty}a_nx^n.

Multiplying a recurrence by $x^n$ and summing over its valid indices converts shifts in the sequence into algebraic operations on $A(x)$ . Initial terms must be accounted for separately. The series can be treated formally, so these manipulations need not depend on analytic convergence. (math.libretexts.org)

For the Fibonacci sequence, the recurrence gives

A(x)-xA(x)-x^2A(x)=x,

and hence

A(x)=\frac{x}{1-x-x^2}.

Factoring the denominator and expanding the resulting fractions using geometric series recovers the explicit formula. More generally, generating functions translate a problem about indexed terms into one about algebraic expressions, after which coefficients are extracted to recover the sequence. (math.libretexts.org)

Algorithm analysis

In computer science, recurrences often describe running time rather than individual numerical sequences. A divide-and-conquer algorithm that creates $a$ subproblems of size approximately $n/b$ , with additional work $f(n)$ , commonly leads to

T(n)=aT(n/b)+f(n).

Base cases and integer rounding complete the specification. For merge sort, the usual recurrence is $T(n)=2T(n/2)+\Theta(n)$ , giving $\Theta(n\log n)$ running time. Binary search instead gives $T(n)=T(n/2)+\Theta(1)$ , resulting in $\Theta(\log n)$ . (ocw.mit.edu)

Methods include repeated expansion, guessing a bound and proving it by induction, and summing work over a recursion tree. The master theorem handles many recurrences of the displayed divide-and-conquer form by comparing $f(n)$ with $n^{\log_b a}$ . Its cases have specific growth and regularity conditions; it is not a universal method for arbitrary recurrences. In algorithm analysis, such complexity bounds are often more useful than exact formulas, because they characterize growth while suppressing implementation-dependent constants. (live.ocw.mit.edu)