|
|
|
Viewing Version
4
of
'recurrence relation'
|
[ view 'recurrence relation'
|
back to history
]
| Title of object: |
recurrence relation |
| Canonical Name: |
RecurrenceRelation |
| Type: |
Definition |
| Created on: |
2001-11-04 07:20:20 |
| Modified on: |
2005-11-27 03:01:43 |
| Classification: |
msc:11B37, msc:03D20 |
| Synonyms: |
recurrence relation=difference equation |
Revision comment (for changes between this and next version):
added example
edited paragraphs (indenting was off in page images mode) |
Preamble:
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xypic} |
Content:
A \emph{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
$$ 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
$$ 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
$$ 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. |
|
|
|
|
|
