## You are here

Homerecurrence relation

## Primary tabs

# 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 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 *$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 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.

## Mathematics Subject Classification

03D20*no label found*11B37

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections