# 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 |