# n-term recurrences

William Lee Irwin III wli@holomorphy.com
Fri, 16 May 2003 14:51:37 -0700

```-- coefs starts with constant term, then coef of a(n-k) in k-term
-- recurrence and goes up by indices
-- vals starts with x0 and goes up by indices
-- solves linear recurrences
-- where xs !! (n+1) = head coefs +
-- sum (zipWith (*) (tail coefs) [xs !! k | k <- [n - length coefs - 1..n]])
-- and the first few terms are given by xs !! n = vals !! n

recurrence coefs vals
| length coefs /= length vals + 1 =
error "mismatched lengths of coefficients and values"
| otherwise = vals ++ map coefSum ys
where
xs = recurrence coefs vals
ys = transpose [drop k xs | k <- [0..length coefs - 1]]
coefSum xs = head coefs + sum (zipWith (*) (tail coefs) xs)
transpose xs = map head xs : transpose (map tail xs)

-- This could be used, say, to generate the list of orthonormal
-- polynomials generated by a three-term recurrence and then
-- expand some function in a function series via Gaussian quadrature.
-- e^(-x^2/2)H_n(x) or e^(-x^c/2)L^c_n(x) look especially attractive.
-- OTOH that tactic may not be numerically useful, or useful only
-- when the function series expansion is known a priori.
-- It could also be a fancier way to generate Fibonacci numbers or
-- Apery numbers or whatever.

-- Not terribly deep, but it amused me for a few minutes to think of it.

-- wli

```