mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, and especially in

numerical analysis Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...

, a homogeneous linear three-term recurrence relation (TTRR, the qualifiers "homogeneous linear" are usually taken for granted) is a

recurrence relation In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...

of the form :

y_=a_n y_n + b_n y_

for

n=1,2,...,

where the sequences

\

and

\

, together with the initial values

y_0, y_1

govern the evolution of the sequence

\

Applications

If the

\

and

\

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 In mathematics, the Fibonacci sequence is a Integer sequence, sequence in which each element is the sum of the two elements that precede it. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted . Many w ...

, which has constant coefficients

a_n=b_n=1

Orthogonal polynomials In mathematics, an orthogonal polynomial sequence is a family of polynomials such that any two different polynomials in the sequence are orthogonal In mathematics, orthogonality (mathematics), orthogonality is the generalization of the geom ...

''P''_''n'' all have a TTRR with respect to degree ''n'', :

P_n(x) = (A_n x + B_n) P_(x) + C_n P_(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 function Special functions are particular mathematical functions that have more or less established names and notations due to their importance in mathematical analysis, functional analysis, geometry, physics, or other applications. The term is defined by ...

s have TTRRs. For example, the solution to :

J_=\fracJ_n-J_

is given by the

Bessel function Bessel functions, named after Friedrich Bessel who was the first to systematically study them in 1824, are canonical solutions of Bessel's differential equation x^2 \frac + x \frac + \left(x^2 - \alpha^2 \right)y = 0 for an arbitrary complex ...

J_n=J_n(z)

. TTRRs are an important tool for the numeric computation of special functions. TTRRs are closely related to continuous 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

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

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 Numerical analysis

Applications

Solution

See also

Literature

References