recurrence relation


A recurrence relationMathworldPlanetmath is an equation which gives the value of an element of a sequenceMathworldPlanetmath 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 sn, then the next value of the sequence expressed as a recurrence relation would be of the form

sn+1=f(s1,s2,,sn-1,sn,n)

where f is any function.

If k is a positive integer, then a sequence s satisfies a kth order recurrence relation if sn+1 can be written in terms of sn,,sn-k+1 whenever n+1>k. In other words, the recurrence relation for s is of the form

sn-1=f(sn-k+1,,sn-1,sn,n)

for some function f.

An example of a recurrence relation is

sn+1=sn+(n+1),

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

sn=sn-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 sequenceMathworldPlanetmath satisfies the recurrence relation

sn+1=sn+sn-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