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,\mathrm{\dots },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,\mathrm{\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},\mathrm{\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