
recurrence relation

(Definition)


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 of a sequence is denoted by , then the next value of the sequence expressed as a recurrence relation would be of the form
where is any function. An example of a simple recurrence relation is
which is the recurrence relation for the sum of the integers from to . This could also be expressed as
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.

Anyone with an account can edit this entry. Please help improve it!
"recurrence relation" is owned by rspuzio. [ full author list (2)  owner history (2) ]


(view preamble)
See Also: BerlekampMassey algorithm, equation, finite difference
Other names: 
difference equation 
Crossreferences: indices, integers, sum, function, current, index, terms, sequence, equation
There are 35 references to this entry.
This is version 4 of recurrence relation, born on 20011104, modified 20051127.
Object id is 664, canonical name is RecurrenceRelation.
Accessed 11605 times total.
Classification:
AMS MSC:  11B37 (Number theory :: Sequences and sets :: Recurrences)   03D20 (Mathematical logic and foundations :: Computability and recursion theory :: Recursive functions and relations, subrecursive hierarchies) 



Pending Errata and Addenda







