Editing Recurrence relation (section)

{{Short description|Pattern defining an infinite sequence of numbers}}
<!-- Lead needs additional context and examples to provide an introduction for beginners. (January 2022) -->
In [[mathematics]], a '''recurrence relation''' is an [[equation]] according to which the <math>n</math>th term of a [[sequence]] of numbers is equal to some combination of the previous terms. Often, only <math>k</math> previous terms of the sequence appear in the equation, for a parameter <math>k</math> that is independent of <math>n</math>; this number <math>k</math> is called the ''order'' of the relation. If the values of the first <math>k</math> numbers in the sequence have been given, the rest of the sequence can be calculated by repeatedly applying the equation.

In ''linear recurrences'', the {{mvar|n}}th term is equated to a [[linear function]] of the <math>k</math> previous terms. A famous example is the recurrence for the [[Fibonacci number]]s,
<math display=block>F_n=F_{n-1}+F_{n-2}</math>
where the order <math>k</math> is two and the linear function merely adds the two previous terms. This example is a [[linear recurrence with constant coefficients]], because the coefficients of the linear function (1 and 1) are constants that do not depend on <math>n.</math> For these recurrences, one can express the general term of the sequence as a [[closed-form expression]] of <math>n</math>. As well, [[P-recursive equation|linear recurrences with polynomial coefficients]] depending on <math>n</math> are also important, because many common [[elementary functions]] and [[special functions]] have a [[Taylor series]] whose coefficients satisfy such a recurrence relation (see [[holonomic function]]).

Solving a recurrence relation means obtaining a [[closed-form solution]]: a non-recursive function of <math>n</math>.

The concept of a recurrence relation can be extended to [[multidimensional array]]s, that is, [[indexed families]] that are indexed by [[tuple]]s of [[natural number]]s.