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
Previous Page Next Page