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
_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.
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
= hj, ij = l,... ,n.
Any sequence satisfying the given recurrence relation can be uniquely represented
as a linear combination
a(x) Y^a(z)ai(x)7 x G N
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
Previous Page Next Page