A recurrence relation for the sequence
is an equation
relating the term
to certain of the preceding
,
, for each ![]()
The recurrence
relation is linear if it expresses
as a linear function of a
fixed number of preceding terms. Otherwise the relation is nonlinear.
The recurrence
relation is kth-order if
can be expressed in terms of
.
The recurrence
relation is homogeneous if the zero sequence
satisfies the
relation. Otherwise the relation is nonhomogeneous.
A kth-order linear
homogeneous recurrence relation with constant coefficients is an
equation of the form
,
, where the Ci are real constants with Cn ≠ 0, Cn-k ≠ 0. Initial conditions for this recurrence relation specify
particular values for k of the ai ( typically
).
Facts:
1. A kth-order linear
homogeneous recurrence relation with constant coefficients can also be written
,
.
2. There are in
general an infinite number of solution sequences
to a kth-order linear
homogeneous recurrence relation (with constant coefficients).
3. A kth-order linear
homogeneous recurrence relation with constant coefficients together with k initial conditions on consecutive
terms
uniquely determines
the sequence
. This is not necessarily the case for nonlinear relations
(see Example 2) or when nonconsecutive initial conditions are specified (see
Example 3).
4. The same
recurrence relation can be written in different forms by adjusting the
subscripts. For examples, the recurrence relation
,
, can be written as
,
.
Examples:
1. The relation
,
, is nonlinear homogeneous recurrence relation with constant
coefficients. If the initial
conditions
,
are imposed, this
defines an unique sequence
whose first few terms
are 0, 1, 1, -1, -1, 3, 11, 115, . . . .
2. The first-order
(constant coefficient) recurrence relation
,
is nonhomogeneous
and non linear. Even though one initial condition are
specified, this does not uniquely specify a solution sequence. Namely, the two
sequences 1, -2, 1, 2, . . . and 1, -2, -1,
, . . . satisfy the
recurrence relation and given initial
condition.
3. The second-order
recurrence relation
,
, with nonconsecutive initial conditions
does not uniquely
specify a solution sequence. Both
and
satisfy the recurrence relation and given initial condition.