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
y_{n+1}=a_n y_n + b_n y_{n-1}forn=1,2,...,
where the sequences \{a_n\} and \{b_n\}, together with the initial values y_0, y_1 govern the evolution of the sequence \{y_n\}.
Applications
If the \{a_n\} and \{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.
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)
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}=\frac{2n}{z}J_n-J_{n-1}
is given by the Bessel function 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.[2]
See also
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)