Recurrence relation

In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, a recurrence relation is an <a href="/facts/Equation/pxFzLAVR">equation</a> according to which the 
 
 
 
 n
 
 
 {\displaystyle n}
 
th term of a <a href="/facts/Sequence/gV2S4uqp">sequence</a> of numbers is equal to some combination of the previous terms. Often, only 
 
 
 
 k
 
 
 {\displaystyle k}
 
 previous terms of the sequence appear in the equation, for a parameter 
 
 
 
 k
 
 
 {\displaystyle k}
 
 that is independent of 
 
 
 
 n
 
 
 {\displaystyle n}
 
; this number 
 
 
 
 k
 
 
 {\displaystyle k}
 
 is called the order of the relation. If the values of the first 
 
 
 
 k
 
 
 {\displaystyle k}
 
 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 <a href="/facts/Linear_function/Ejvy8CKy">linear function</a> of the 
 
 
 
 k
 
 
 {\displaystyle k}
 
 previous terms. A famous example is the recurrence for the <a href="/facts/Fibonacci_number/mqxpAUQD">Fibonacci numbers</a>,

F
          
            n
          
        
        =
        
          F
          
            n
            −
            1
          
        
        +
        
          F
          
            n
            −
            2
          
        
      
    
    {\displaystyle F_{n}=F_{n-1}+F_{n-2}}

where the order 
 
 
 
 k
 
 
 {\displaystyle k}
 
 is two and the linear function merely adds the two previous terms. This example is a <a href="/facts/Linear_recurrence_with_constant_coefficients/gs9PR0D7">linear recurrence with constant coefficients</a>, because the coefficients of the linear function (1 and 1) are constants that do not depend on 
 
 
 
 n
 .
 
 
 {\displaystyle n.}
 
 For these recurrences, one can express the general term of the sequence as a <a href="/facts/Closed-form_expression/y0xCXlSk">closed-form expression</a> of 
 
 
 
 n
 
 
 {\displaystyle n}
 
. As well, <a href="/facts/P-recursive_equation/U03dgoPw">linear recurrences with polynomial coefficients</a> depending on 
 
 
 
 n
 
 
 {\displaystyle n}
 
 are also important, because many common <a href="/facts/Elementary_functions/wVFyDwu8">elementary functions</a> and <a href="/facts/Special_functions/JETSeucA">special functions</a> have a <a href="/facts/Taylor_series/M0aTuftH">Taylor series</a> whose coefficients satisfy such a recurrence relation (see <a href="/facts/Holonomic_function/eaVU0RNs">holonomic function</a>).
Solving a recurrence relation means obtaining a <a href="/facts/Closed-form_solution/y0xCXlSk">closed-form solution</a>: a non-recursive function of 
 
 
 
 n
 
 
 {\displaystyle n}
 
.
The concept of a recurrence relation can be extended to <a href="/facts/Multidimensional_array/gHJJ3XPw">multidimensional arrays</a>, that is, <a href="/facts/Indexed_families/aFqfzJN0">indexed families</a> that are indexed by <a href="/facts/Tuple/BI1HIxL8">tuples</a> of <a href="/facts/Natural_number/u65og8JE">natural numbers</a>.

Recurrence relation open-in-new

Recurrence relation