Definitions and Techniques
Our study begins with the basic properties of recurrence sequences, and the
particular properties of linear recurrence sequences. The collection of all linear
recurrences associated to a given polynomial is introduced, and a group structure on
this collection described. The far-reaching description of linear recurrence sequences
as generalized power sums is given, and some deeper topics like non-degeneracy and
the problem of characterizing those subsequences of a linear recurrence sequence
that are also linear recurrence sequences are mentioned.
The elementary observation that the formal power series associated to a se-
quence is rational if and only if the sequence is a linear recurrence sequence is
made, and related to other problems like characterizing the Taylor expansions of
solutions of linear ordinary differential equations. The problem of recognizing ratio-
nality in a power series is discussed, and basic tools from p-adic analysis introduced
to give a proof of a simple case of the Hadamard Quotient Theorem.
Finally, deep results from Diophantine analysis are introduced that will be used
later to understand the growth and other properties of linear recurrence sequences.
1.1. Main Definitions and Principal Properties
1.1.1. Recurrence Sequences. We restrict ourselves initially to linear re-
currence sequences, defined over a commutative ring 1Z with a unit 1. Nonetheless,
many of the results and all the terminology below hold for much more general
algebraic domains. Linearity of the defining recurrence relation is essential, as is
the fact that the coefficients of that relation are constant elements of the ring of
definition. The qualifier 'linear' will therefore be omitted unless it is needed for
A linear recurrence sequence is a sequence a = (a{x)) of elements of 1Z satisfying
a homogeneous linear recurrence relation
(1.1) a(x -f n) = s\a(x -h n 1) + + sn-ia(x + 1) -h sna(x), x G N
with constant coefficients Sj £ 1Z, the coefficient ring. We will suppose throughout
that sn is not a zero divisor in 1Z.
1.1.2. Characteristic Polynomial. The polynomial
=Xn- SlXn~x
sn.xX - sn
associated to the relation (1.1) is called its characteristic polynomial, and the rela-
tion is said to be of order n.
If TZ is a ring without zero divisors then any linear recurrence sequence a
satisfies a recurrence relation of minimal length. The characteristic polynomial
of the minimal length relation is the minimal polynomial of the sequence a. The
degree of that minimal polynomial is said to be the order of the linear recurrence
Previous Page Next Page