2 1. DEFINITIONS AND TECHNIQUES

sequence a. The minimal polynomial of the sequence a divides the characteristic

polynomial of a.

Linear recurrence sequences of order 2 and 3 are called binary and ternary

linear recurrence sequences respectively, and sequences over Z, Q, Q, M, C and

Qp respectively are known as integer, rational, algebraic, real, complex and p-adic

linear recurrence sequences.

Inhomogeneous linear recurrence relations take the form

a(x -f n) = s\a(x + n — 1) + • • • + sn-\a(x -f 1) + sna(x) -f sn+i, x G Z

+

.

Such a sequence a then satisfies the homogeneous recurrence relation

n - l

a(x + n -f 1) = (si + l)a(x + n) -f TJ(s^

+

i — fi)a(x + n — i) — sna(x)

2 = 1

of order n + 1, with characteristic polynomial

F(X) = (X n - SiX™-1

Sn

_xX - sn)(X - 1).

1.1.3. Initial Values. For a linear recurrence sequence defined by a recur-

rence relation (1.1) of order n the elements a(l),.. . , a(n) are called the initial

values; they determine all other elements of the sequence. Further, if sn is an in-

vertible element of 1Z then the sequence may be continued in the opposite direction,

yielding a(0), a ( - l ) , a ( - 2 ) , . . . .

1.1.4. Set of Solutions of a Recurrence Relation over a Field. Given

a polynomial / defined over a field, consider the set C(f) of all possible linear

recurrence sequences satisfying the equation (1.1), and the set £*(/) of all sequences

for which / is their characteristic polynomial. If g is a divisor of / then C(g) C £(/) .

If/ is irreducible, then £*(f) contains all sequences from C(f) except the identically

zero sequence.

THEOREM

1.1. Let f and g be two polynomial defined over a field. Then

• {(c(x)) : c(x) = a{x) + b(x) a G £(/) , b G C(g)} = C(lcm(f,g));

• C(f)nC(g) = C(gcd(f,g));

• £(/ ) C C(g) if and only iff\g.

For finite fields these results can be found in [671] or in [1378]; it is readily

checked that the proofs do not depend on the characteristic.

If c(x) = a(x)b(x), a G £(/) , b G C{g), then c is again a linear recurrence

sequence, but describing its characteristic polynomial is not immediate. This will

be dealt with in Chapter 4 below.

The set C(f) is a linear space of dimension n in the following sense. Consider

the n basic sequences ai — the impulse sequences — with initial values

aiU)

= hj, ij = l,... ,n.

Any sequence satisfying the given recurrence relation can be uniquely represented

as a linear combination

n

a(x) — Y^a(z)ai(x)7 x G N

i=l

of the relevant set of impulse sequences. To see this, notice that the right-hand

side satisfies the relation (1.1), as does any linear combination of solutions of the