View source for Three-term recurrence relation

{{Multiple issues|
{{More footnotes|date=October 2024}}
{{Context|date=October 2024}}
}}
In [[mathematics]], and especially in [[numerical analysis]], a '''homogeneous linear three-term recurrence relation''' ('''TTRR''', the qualifiers "homogeneous linear" are usually taken for granted)<ref>Gi, Segura, Temme (2007), Chapter 4.1</ref> is a [[recurrence relation]] of the form
:<math>y_{n+1}=a_n y_n + b_n y_{n-1}</math> for <math>n=1,2,...,</math>
where the sequences <math>\{a_n\}</math> and <math>\{b_n\}</math>, together with the initial values <math>y_0, y_1</math> govern the evolution of the sequence <math>\{y_n\}</math>.

== Applications ==

If the <math>\{a_n\}</math> and <math>\{b_n\}</math> are constant and independent of the step index ''n'', then the TTRR is a [[linear recurrence with constant coefficients#Order 2|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 <math>a_n=b_n=1</math>.

[[Orthogonal polynomials]] ''P''<sub>''n''</sub> all have a TTRR with respect to degree ''n'',
:<math> P_n(x) = (A_n x + B_n) P_{n-1}(x) + C_n P_{n-2}(x)</math>
where ''A<sub>n</sub>'' 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 function]]s have TTRRs. For example, the solution to
:<math>J_{n+1}=\frac{2n}{z}J_n-J_{n-1}</math>
is given by the [[Bessel function]] <math>J_n=J_n(z)</math>. TTRRs are an important tool for the numeric computation of special functions.

TTRRs are closely related to [[continuous fraction]]s.

== 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 <math>y_0, y_1</math>.<ref>Gi, Segura, Temme (2007), Chapter 4.1</ref>

==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==
{{Reflist}}

[[Category:Numerical analysis]]