Editing Recurrence relation (section)

==Definition==
A ''recurrence relation'' is an equation that expresses each element of a [[sequence]] as a function of the preceding ones. More precisely, in the case where only the immediately preceding element is involved, a recurrence relation has the form
:<math>u_n=\varphi(n, u_{n-1})\quad\text{for}\quad n>0,</math>
where 
:<math>\varphi:\mathbb N\times X \to X</math>
is a function, where {{mvar|X}} is a set to which the elements of a sequence must belong. For any <math>u_0\in X</math>, this defines a unique sequence with <math>u_0</math> as its first element, called the ''initial value''.<ref>Jacobson, Nathan, Basic Algebra 2 (2nd ed.), § 0.4. pg 16.</ref>

It is easy to modify the definition for getting sequences starting from the term of index 1 or higher.

This defines recurrence relation of ''first order''. A recurrence relation of ''order'' {{mvar|k}} has the form 
:<math>u_n=\varphi(n, u_{n-1}, u_{n-2}, \ldots, u_{n-k})\quad\text{for}\quad n\ge k,</math>

where <math>\varphi: \mathbb N\times X^k \to X</math> is a function that involves {{mvar|k}} consecutive elements of the sequence.
In this case, {{mvar|k}} initial values are needed for defining a sequence.