---
tag: XWJ786Z701
kind: definition
name: Three-term recurrence relation
msc: [39A06, 33C45]
defines: NFJTRCRB9W
uses: [8Y28JQB0Q5, 0G9EKM0E15]
sources:
  - url: https://en.wikipedia.org/wiki/Recurrence_relation
---

## Definition

Let $K$ be a field, and let $a_n, b_n, c_n \in K$ for $n \ge 1$ be given, with $a_n \ne 0$ and $c_n \ne 0$ for all $n$.
A *three-term recurrence relation* is the homogeneous [[linear recurrence|8Y28JQB0Q5]]
$$a_n\, u_{n+1} + b_n\, u_n + c_n\, u_{n-1} = 0 \qquad (n \ge 1)$$
for a [[sequence|0G9EKM0E15]] $(u_n)_{n \ge 0}$ in $K$.

## Remarks

Example: the [[Chebyshev polynomials|M6EAR1JHPP]] satisfy $T_{n+1}(x) - 2x\, T_n(x) + T_{n-1}(x) = 0$ in $\R[x]$, here read in the field $\R(x)$ of rational functions with $a_n = 1$, $b_n = -2x$, $c_n = 1$.
Check for $n = 1$: $T_2(x) = 2x^2 - 1 = 2x \cdot x - 1$.
Non-example: $u_{n+1} = u_n + u_{n-1} + u_{n-2}$ links four terms, so it is not a three-term recurrence.
The condition $a_n \ne 0$ lets one solve for $u_{n+1}$, and $c_n \ne 0$ makes the order exactly two; so the solutions form a $K$-vector space of dimension $2$, fixed by $u_0$ and $u_1$.
A common normalized form is $u_{n+1} = (x - \alpha_n) u_n - \beta_n u_{n-1}$, which is the [[three-term recurrence for orthogonal polynomials|YRYWCP9TYV]].