Notes

Chapter 4: Systems Based on Numbers

Section 3: Recursive Sequences


Recurrence relations

The rules for the sequences given here all have the form of linear recurrence relations. An explicit formula for the nth term in each sequence can be found by solving the algebraic equation obtained by applying the replacement f[m_] -> tm to the recurrence relation. (In case (e), for example, the equation is tn == -tn-1 + tn-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.


From Stephen Wolfram: A New Kind of Science [citation]