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

wherea andb are functions ofx 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.

NB: before using any of the recurrences below, see the next post for a numerical pitfall to avoid.

Bessel functions of the first and second kind:

Modified Bessel functions of the first and second kind:

Chebyshev polynomials of the first and second kind:

Hermite polynomials (physicists' convention):

Legendre polynomials:

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

The post Three-term recurrences first appeared on John D. Cook.