In mathematics, a recurrence relation is an equation according to which the th term of a sequence of numbers is equal to some combination of the previous terms. Often, only previous terms of the sequence appear in the equation, for a parameter that is independent of ; this number is called the order of the relation. If the values of the first numbers in the sequence have been given, the rest of the sequence can be calculated by repeatedly applying the equation.
In linear recurrences, the nth term is equated to a linear function of the previous terms. A famous example is the recurrence for the Fibonacci numbers,
Solving a recurrence relation means obtaining a closed-form solution: a non-recursive function of .
The concept of a recurrence relation can be extended to multidimensional arrays, that is, indexed families that are indexed by tuples of natural numbers.
© MMXXIII Rich X Search. We shall prevail. All rights reserved. Rich X Search