Recurrence relations

The rules for the sequences given here all have the form of linear recurrence relations. An explicit formula for the n^th term in each sequence can be found by solving the algebraic equation obtained by applying the replacement f[m_]  t^m to the recurrence relation. (In case (e), for example, the equation is tⁿ  -t^{n - 1} + t^{n - 2}.) Note that (d) is the Fibonacci sequence, discussed on page 890.

Standard examples of recursive sequences that do not come from linear recurrence relations include factorial

f[1] = 1; f[n_] := n f[n - 1]

and Ackermann functions (see below). These two sequences both grow rapidly, but smoothly.

A recurrence relation like

f[0] = x; f[n_] := a f[n - 1] (1 - f[n - 1])

corresponds to an iterated map of the kind discussed on page 920, and has complicated behavior for many rational x.