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 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.
for some function .
An example of a 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. Note that this is a first order recurrence relation.
As another example of a recurrence relation, the Fibonacci sequence satisfies the recurrence relation
Note that this is a second order recurrence relation.
|Date of creation||2013-03-22 11:56:04|
|Last modified on||2013-03-22 11:56:04|
|Last modified by||rspuzio (6075)|