Three-term recurrence relation

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (October 2024) (Learn how and when to remove this message) This article provides insufficient context for those unfamiliar with the subject. Please help improve the article by providing more context for the reader. (October 2024) (Learn how and when to remove this message) (Learn how and when to remove this message)

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

${\displaystyle y_{n+1}=a_{n}y_{n}+b_{n}y_{n-1}}$ for ${\displaystyle n=1,2,...,}$

where the sequences ${\displaystyle \{a_{n}\}}$ and ${\displaystyle \{b_{n}\}}$, together with the initial values ${\displaystyle y_{0},y_{1}}$ govern the evolution of the sequence ${\displaystyle \{y_{n}\}}$.

If the ${\displaystyle \{a_{n}\}}$ and ${\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 ${\displaystyle a_{n}=b_{n}=1}$.

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

${\displaystyle P_{n}(x)=(A_{n}x+B_{n})P_{n-1}(x)+C_{n}P_{n-2}(x)}$

where A_n 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

${\displaystyle J_{n+1}={\frac {2n}{z}}J_{n}-J_{n-1}}$

is given by the Bessel function ${\displaystyle J_{n}=J_{n}(z)}$. TTRRs are an important tool for the numeric computation of special functions.

TTRRs are closely related to continuous fractions.

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 ${\displaystyle y_{0},y_{1}}$.^[2]

• Miller's recurrence algorithm

• 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)