# Three-term recurrence relation

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Three-term_recurrence_relation
> Markdown URL: https://mediated.wiki/source/Three-term_recurrence_relation.md
> Source: https://en.wikipedia.org/wiki/Three-term_recurrence_relation
> Source revision: 1303559846
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [mathematics](/source/Mathematics), and especially in [numerical analysis](/source/Numerical_analysis), a **homogeneous linear three-term recurrence relation** (**TTRR**, the qualifiers "homogeneous linear" are usually taken for granted)[1] is a [recurrence relation](/source/Recurrence_relation) of the form

- y_{n+1}=a_n y_n + b_n y_{n-1} for n=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](/source/Linear_recurrence_with_constant_coefficients#Order_2). Arguably the simplest, and most prominent, example for this case is the [Fibonacci sequence](/source/Fibonacci_sequence), which has constant coefficients a_n=b_n=1.

[Orthogonal polynomials](/source/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 *An* is not 0. Conversely, [Favard's theorem](/source/Favard's_theorem) states that a sequence of polynomials satisfying a TTRR is a sequence of orthogonal polynomials.

Also many other [special functions](/source/Special_function) have TTRRs. For example, the solution to

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

is given by the [Bessel function](/source/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](/source/Continued_fraction).

## Solution

Solutions of a TTRR, like those of a [linear ordinary differential equation](/source/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

- [Miller's recurrence algorithm](/source/Miller's_recurrence_algorithm)

## Literature

- [Walter Gautschi](/source/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](/source/Nico_M._Temme). Numerical Methods for Special Functions. siam (2007)
- J. Wimp, Computation with recurrence relations, London: Pitman (1984)

## References

1. Gi, Segura, Temme (2007), Chapter 4.1

1. Gi, Segura, Temme (2007), Chapter 4.1

---
Adapted from the Wikipedia article [Three-term recurrence relation](https://en.wikipedia.org/wiki/Three-term_recurrence_relation) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Three-term_recurrence_relation?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.