A given infinite
sequence
can often be
represented in a more useful or more compact form. Namely, there may be a
closed form expression for
as a function of n, the terms of the sequence may appear
as coefficients in a simple generating function, or the sequence may be
specified by a recurrence relation. Each representation has advantages, in
either defining the sequence or establishing information about its terms.
Definitions:
A sequence
is a function from the set of nonnegative
integers to the real numbers (often the integers). The terms of the sequence
are the values
.
A closed
form for the sequences
is an algebraic
expression for
as a function of n.
A recurrence
relation is an equation expressing a term of a sequence as a function of prior terms in the
sequence.
A solution
of a recurrence relation is a
sequence whose terms satisfy the relation.
The generating
function for the sequence
is the function
or any equivalent closed form
expression.
The exponential
generating function for the sequence
is the function
or any equivalent closed form
expression.
Examples:
1. The Fibonacci
numbers Fn arise in many applications and
are given by the sequence 0, 1, 2, 3, 5, 8, 13, . . . . This infinite sequence can be finitely
encoded by means of the recurrence relation
Fn = Fn-1 +
Fn-2 , n³2, with F0 = 0 and F1 = 1.
Alternatively, a
closed form expression for this sequence is given by
![]()
The Fibonacci
numbers can be represented in a third way, via the generating function
Namely,
when this rational function is expanded in powers of x, the resulting coefficients generate the sequence values Fn:
![]()
2. Lucas numbers
are produced by
the recursive definition
,
, n³2.