A sequence is a function from a subset of the set of integers (usually either the set or the set to a set . We use the notation to denote the image of the integer . We call a term of the sequence.
Unlike sets, the elements in a sequence can be duplicate and they have a particular order.
Sequences of the form are often used in computer science. These finite sequences are also called strings. This string is also denoted by The length of a string is the number of terms in this string. The empty string, denoted by , is the string that has no terms. The empty string has length zero.
A geometric progression is a sequence of the form
where the initial term and the common ratio are real numbers.
It is a discrete analogue of the exponential function .
An arithmetic progression is a sequence of the form
where the initial term and the common difference are real numbers.
It is a discrete analogue of the linear function .
A recurrence relation for the sequence is an equation that expresses in terms of one or more of the previous terms of the sequence, namely, , for all integers with , where is a nonnegative integer. A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation.
The initial conditions for a recursively defined sequence specify the terms that precede the first term where the recurrence relation takes effect.
For example, the Fibonacci sequence, , is defined by the initial conditions , and the recurrence relation
for .
An explicit formula for the terms of a sequence, called a closed formula, solves a recurrence relation together with it's initial conditions.
Let be a sequence that satisfies the recurrence relation for , and suppose that .
Starting with the initial condition , and working upward until we reach to deduce a closed formula for the sequence. We see that
We can also work in the opposite direction, starting from and working downwards.