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 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.


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