PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
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 $ 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

$\displaystyle s_{n+1} = f(s_1,s_2,\ldots,s_{n-1},s_n,n) $

where $ f$ is any function. An example of a simple recurrence relation is

$\displaystyle 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

$\displaystyle 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.



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)

View style:

See Also: Berlekamp-Massey algorithm, equation, finite difference

Other names:  difference equation

Cross-references: 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 2001-11-04, modified 2005-11-27.
Object id is 664, canonical name is RecurrenceRelation.
Accessed 11605 times total.

Classification:
AMS MSC11B37 (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
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
rate | post | correct | update request | add derivation | add example | add (any)