Three-term recurrences

There many examples of families of functions where each function can be computed as a linear combination of the two previous terms

$f_{n+1}(x) = a(x) f_n(x) + b(x) f_{n-1}(x)$

where a and b are functions of x but not on n. This is called a three-term recurrence formula.

It’s amazing how often you can run into three-term recurrence formulas. There are theorems that give conditions for such recurrences to hold, but I haven’t reached the bottom of that rabbit hole [1].

For this post I just want to give examples.

Bessel functions of the first and second kind:

$\begin{align*} J_{\nu+1}(x) &= \frac{2\nu}{x}\,J_\nu(x) - J_{\nu-1}(x) \\ Y_{\nu+1}(x) &= \frac{2\nu}{x}\,Y_\nu(x) - Y_{\nu-1}(x) \end{align*}$

Modified Bessel functions of the first and second kind:

$\begin{align*} I_{\nu+1}(x) &= I_{\nu-1}(x) - \frac{2\nu}{x}\,I_\nu(x) \\ K_{\nu+1}(x) &= K_{\nu-1}(x) + \frac{2\nu}{x}\,K_\nu(x) \end{align*}$

Chebyshev polynomials of the first and second kind:

$\begin{align*} T_{n+1}(x) &= 2x\,T_n(x) - T_{n-1}(x) \\ U_{n+1}(x) &= 2x\,U_n(x) - U_{n-1}(x) \end{align*}$

Hermite polynomials (physicists’ convention):

$H_{n+1}(x) = 2x\,H_n(x) - 2n\,H_{n-1}(x)$

Legendre polynomials:

$P_{n+1}(x) = \frac{2n+1}{n+1}\,x\,P_n(x) - \frac{n}{n+1}\,P_{n-1}(x)$

[1] See Bochner’s theorem for orthogonal polynomials, the Nikiforov–Uvarov method, and Infeld-Hull factorization.

Leave a Reply