6 1. DEFINITIONS AND TECHNIQUES

1.1.11. Rational functions. Linear recurrence sequences arise naturally as

sequences of Taylor coefficients of rational functions; see [1025]. Given a polynomial

/ of degree n define the reciprocal polynomial f~ by f~(X) = Xnf(X~1).

T H E O R E M 1.5. A sequence a satisfies the recurrence relation (1.1) with charac-

teristic polynomial f G H[X] if and only if it is the sequence of Taylor coefficients

of a (formal) power series representing a rational function r(X)/f~~(X), where r

is a polynomial of degree less than n determined by the initial values of a.

To see this, note that on comparing coefficients of XnJrX, for x = 0 , 1 , . . . ,

oo

x=l

holds if and only if (1.1) holds.

To test an arbitrary sequence a of elements of a field F for the property of being

a linear recurrence sequence, consider the Kronecker-Hankel determinants

±N.

n

(a) = d e t ( a ( n + z+j))oi, j

N'

T H E O R E M 1.6. The sum f{z) — Y^=oanZn represents a rational function if

and only if for some n, AAr?n(a) = 0 for all sufficiently large N.

An excellent account of this is given in [620].

PROOF. We prove one implication in the case where n = 0. If / is rational, then

/(*)

k £

2 = 0

]riZ1/

/ V

-J

J =0

SjZJ

with SQ 7^ 0. Multiplying through by s(z) = J2j=osjz^ shows that all the linear

combinations

soaL + siciK-i H \~ siaK-£

vanish if L exceeds k and H. This shows that Ajvrn(a) = 0 because, from some point

on, all the columns can be expressed as linear combinations of the early columns.

For the converse, work backwards from the vanishing of the determinant to obtain

the linear recurrence relation, see [620]. •

1.1.12. Power s of matrices. Consider an arbitrary square matrix M defined

over 11, with the z, j-th. entry of Mx written rriij (x). The Cayley-Hamilton theorem

asserts that for each z, j the sequence rriij is a linear recurrence sequence satisfying

a recurrence whose characteristic polynomial is the characteristic polynomial of M.

Accordingly, let a denote the linear recurrence sequence satisfying (1.1) and

write A(x) for the row-vector (a(x),.. . , a(x + n — 1)). Let

0 .. . 0 fn \

F =

t 0

1

0

\ 0 0 0

be the companion matrix of (1.1). Then

A(x) = A(x-l)T =

A(0)Fx,

fn-l

fn-2

h J

l € Z

H