# recurrence relation

A recurrence relation is an equation which gives the value of an element of a sequence in terms of the values of the sequence for smaller values of the position index and the position index itself. If the position $n$ of a sequence $s$ is denoted by $s_{n}$, then the next value of the sequence expressed as a recurrence relation would be of the form

 $s_{n+1}=f(s_{1},s_{2},\ldots,s_{n-1},s_{n},n)$

where $f$ is any function.

If $k$ is a positive integer, then a sequence $s$ satisfies a $k$th order recurrence relation if $s_{n+1}$ can be written in terms of $s_{n},\dots,s_{n-k+1}$ whenever $n+1>k$. In other words, the recurrence relation for $s$ is of the form

 $s_{n-1}=f(s_{n-k+1},\dots,s_{n-1},s_{n},n)$

for some function $f$.

An example of a recurrence relation is

 $s_{n+1}=s_{n}+(n+1),$

which is the recurrence relation for the sum of the integers from $1$ to $n+1$. This could also be expressed as

 $s_{n}=s_{n-1}+n$

keeping in mind that, as long as we set the proper initial values of the sequence, the recurrence relation indices can have any constant amount added or subtracted. Note that this is a first order recurrence relation.

As another example of a recurrence relation, the Fibonacci sequence satisfies the recurrence relation

 $s_{n+1}=s_{n}+s_{n-1}.$

Note that this is a second order recurrence relation.

 Title recurrence relation Canonical name RecurrenceRelation Date of creation 2013-03-22 11:56:04 Last modified on 2013-03-22 11:56:04 Owner rspuzio (6075) Last modified by rspuzio (6075) Numerical id 13 Author rspuzio (6075) Entry type Definition Classification msc 03D20 Classification msc 11B37 Synonym difference equation Related topic BerlekampMasseyAlgorithm Related topic Equation Related topic FiniteDifference Defines first order Defines second order Defines kth order