In mathematics, and especially in numerical analysis, a homogeneous linear three-term recurrence relation (TTRR, the qualifiers "homogeneous linear" are usually taken for granted) is a recurrence relation of the form
y n + 1 = a n y n + b n y n − 1 {\displaystyle y_{n+1}=a_{n}y_{n}+b_{n}y_{n-1}} for n = 1 , 2 , . . . , {\displaystyle n=1,2,...,}
where the sequences { a n } {\displaystyle \{a_{n}\}} and { b n } {\displaystyle \{b_{n}\}} , together with the initial values y 0 , y 1 {\displaystyle y_{0},y_{1}} govern the evolution of the sequence { y n } {\displaystyle \{y_{n}\}} .
Applications If the { a n } {\displaystyle \{a_{n}\}} and { b n } {\displaystyle \{b_{n}\}} 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 a n = b n = 1 {\displaystyle a_{n}=b_{n}=1} . Orthogonal polynomials Pn all have a TTRR with respect to degree n,
P n ( x ) = ( A n x + B n ) P n − 1 ( x ) + C n P n − 2 ( x ) {\displaystyle P_{n}(x)=(A_{n}x+B_{n})P_{n-1}(x)+C_{n}P_{n-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
J n + 1 = 2 n z J n − J n − 1 {\displaystyle J_{n+1}={\frac {2n}{z}}J_{n}-J_{n-1}}
is given by the Bessel function J n = J n ( z ) {\displaystyle J_{n}=J_{n}(z)} . TTRRs are an important tool for the numeric computation of special functions. TTRRs are closely related to continued 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 y 0 , y 1 {\displaystyle y_{0},y_{1}} .
See also Miller's recurrence algorithm
Literature Walter Gautschi. Computational Aspects of Three-Term Recurrence Relations. SIAM Review, 9:24–80 (1967). Walter Gautschi. Minimal Solutions of Three-Term Recurrence Relation and Orthogonal Polynomials. Mathematics of Computation, 36:547–554 (1981). Amparo Gil, Javier Segura, and Nico M. Temme. Numerical Methods for Special Functions. siam (2007) J. Wimp, Computation with recurrence relations, London: Pitman (1984)
References
