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^{n} == -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.