Recursive Sequence

A recursive sequence , also known as a recurrence sequence, is a sequence of numbers indexed by an integer and generated by solving a recurrence equation. The terms of a recursive sequences can be denoted symbolically in a number of different notations, such as , , or f[], where is a symbol representing the sequence.

The idea of sequences in which later terms are deduced from earlier ones, which is implicit in the principle of mathematical induction, dates to antiquity.

In the case of linear recurrence equations such as the recurrence

(with ) generating the Fibonacci numbers, it is possible to solve for an explicit analytic form of the th term of the sequence. Some special classes of recurrence equations have analytic solutions for specific parameters, but solutions for a general parameter is not known. An example of this type is the logistic equation

which has known exact solutions only for , 2, and 4. It is not known how to solve a general recurrence equation to produce an explicit form for the terms of the recursive sequence, although computers can often be used to calculate large numbers of terms through brute force (combined with more sophisticated techniques such as caching, etc.).

Historically speaking, the Fibonacci numbers (left top figure), which are one of the most well-known such sequences, predate Leonardo Fibonacci's 1202 discovery by more than a millennium, having arisen around 200 BC in work by Pingala (Wolfram 2002, pp. 890-891). In the late 1800s and early 1900s, investigations into the foundations of mathematics led to the formal definition of so-called recursive functions. However, a systematic investigation of the types of possible behavior was apparently not undertaken until the work of Wolfram (2002), with the exception of a few isolated sequences such as Hofstadter's Q-sequence in 1979 (right top figure) and the Hofstadter-Conway $10,000 sequence in 1988 (bottom figure).

Wolfram Web Resources