three-term recurrence relation

If the $\backslash \{a\_n\backslash \}$ and $\backslash \{b\_n\backslash \}$ 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 P_n 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 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

:$J\_\{n+1\}=\backslash 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 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 $y\_0,\; y\_1$.Gi, Segura, Temme (2007), Chapter 4.1

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

{{Reflist}}

Category:Numerical analysis