recurrence relationRecurrenceRelation2001-11-04 07:20:202008-02-26 20:26:46Definitionfirst ordersecond orderkth order\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xypic}\PMlinkescapeword{order}
\PMlinkescapeword{satisfies}
\PMlinkescapeword{terms}
A \emph{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 \PMlinkescapetext{current} 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 \emph{$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 \PMlinkescapetext{simple} 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.