CHAPTER 1

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

emphasis.

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

f(X)

=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

http://dx.doi.org/10.1090/surv/104/01