Three-term recurrence relation explained

In mathematics, and especially in numerical analysis, a homogeneous linear three-term recurrence relation (TTRR, the qualifiers "homogeneous linear" are usually taken for granted)[1] is a recurrence relation of the form

yn+1=anyn+bnyn-1

for

n=1,2,...,

where the sequences

\{an\}

and

\{bn\}

, together with the initial values

y0,y1

govern the evolution of the sequence

\{yn\}

.

Applications

If the

\{an\}

and

\{bn\}

are constant and independent of the step index n, then the TTRR is a Linear recurrence with constant coefficients of order 2. Arguably the simplest, and most prominent, example for this case is the Fibonacci sequence, which has constant coefficients

an=bn=1

.

Orthogonal polynomials Pn all have a TTRR with respect to degree n,

Pn(x)=(Anx+Bn)Pn-1(x)+CnPn-2(x)

where An is not 0. Conversely, Favard's theorem states that a sequence of polynomials satisfying a TTRR is a sequence of orthogonal polynomials.

Also many other special functions have TTRRs. For example, the solution to

Jn+1=

2n
z

Jn-Jn-1

is given by the Bessel function

Jn=Jn(z)

. TTRRs are an important tool for the numeric computation of special functions.

TTRRs are closely related to continuous fractions.

Solution

Solutions of a TTRR, like those of a linear ordinary differential equation, form a two-dimensional vector space: any solution can be written as the linear combination of any two linear independent solutions. A unique solution is specified through the initial values

y0,y1

.[2]

See also

Literature

Notes and References

  1. Gi, Segura, Temme (2007), Chapter 4.1
  2. Gi, Segura, Temme (2007), Chapter 4.1