TOPICS
Search

Recursive Sequence


A recursive sequence {f(n)}_n, also known as a recurrence sequence, is a sequence of numbers f(n) indexed by an integer n 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 f_n, f(n), or f[n], where f 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

 F_n=F_(n-1)+F_(n-2)

(with F_1=F_2=1) generating the Fibonacci numbers, it is possible to solve for an explicit analytic form of the nth 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

 x_n=rx_(n-1)(1-x_(n-1)),

which has known exact solutions only for r=-2, 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.).

RecursiveSequences

Historically speaking, the Fibonacci numbers F_n (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 Q(n) in 1979 (right top figure) and the Hofstadter-Conway $10,000 sequence a(n) in 1988 (bottom figure).


See also

Hofstadter-Conway $10,000 Sequence, Hofstadter's Q-sequence, Recurrence Equation

Explore with Wolfram|Alpha

References

Wolfram, S. "Recursive Sequences." A New Kind of Science. Champaign, IL: Wolfram Media, pp. 128-131 and 890-891, 2002.

Referenced on Wolfram|Alpha

Recursive Sequence

Cite this as:

Weisstein, Eric W. "Recursive Sequence." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/RecursiveSequence.html

Subject classifications