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
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (210)
Orphanage
Unclass'd (1)
Unproven (473)
Corrections (38)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: Very high
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.

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,\dots,s_{n-k+1}$ whenever $ n+1>k$. In other words, the recurrence relation for $ s$ is of the form

$\displaystyle s_{n-1} = f(s_{n-k+1},\dots,s_{n-1},s_n,n) $
for some function $ f$.

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. Note that this is a first order recurrence relation.

As another example of a recurrence relation, the Fibonacci sequence satisfies the recurrence relation

$\displaystyle s_{n+1} = s_n + s_{n-1}. $
Note that this is a second order recurrence relation.



Anyone with an account can edit this entry. Please help improve it!

"recurrence relation" is owned by rspuzio. [ full author list (3) | owner history (2) ]
(view preamble)

View style:

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

Other names:  difference equation
Also defines:  first order, second order, kth order

Attachments:
formula for sequences satisfying second order recurrence relations (Theorem) by Wkbj79
examples of simple recurrence relations (Example) by PrimeFan
Log in to rate this entry.
(view current ratings)

Cross-references: Fibonacci sequence, indices, sum, integer, positive, function, index, sequence, equation
There are 79 references to this entry.

This is version 8 of recurrence relation, born on 2001-11-04, modified 2008-02-26.
Object id is 664, canonical name is RecurrenceRelation.
Accessed 17472 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
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

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