Next: Characteristic polynomials
Up: Linear recursive sequences
Previous: Recursive definitions
Linear recursive sequences
A sequence
is said to satisfy the linear recurrence
with coefficients , , ...,
if

(2) 
holds for all integers for which this makes sense.
(If the sequence starts with , then this means for .)
The integer is called the order of the linear recurrence.
A linear recursive sequence
is a sequence of numbers
satisfying some linear recurrence as above
with
and
.
For example, the sequence (1) satisfies
for all integers ,
so it is a linear recursive sequence satisfying
a recurrence of order 1,
with and .
Requiring
guarantees that
the linear recurrence can be used to express
as a linear combination of earlier terms:
The requirement
lets one express
as a linear combination of later terms:
This lets one define , , and so on,
to obtain a doubly infinite sequence
that now satisfies the same linear recurrence for all integers ,
positive or negative.
Next: Characteristic polynomials
Up: Linear recursive sequences
Previous: Recursive definitions
Zvezdelina StankovaFrenkel
20000920