SECTION 2.1 Elementary Number Theory 103
Such difference equations can be solved in principle; in fact the gen-
eral solution of (2.7) can be expressed as a polynomial. We shall sum-
marize as a theorem below.^26
Theorem. A sequence u 0 ,u 1 ,u 2 ,...is expressible as a polynomial of
degreek innif and only if itsk-th order differences are constant.
Proof. Assume that thek-th order differences of the sequence
u 0 ,u 1 ,u 2 ,...are constant. We shall prove by induction onk thatun
is expressible as a polynomial of degreek inn. So assume thatk > 1
and that the result is valid whenever we have constant m-th order
differences, wherem < nis a positive integer.
We setv 0 =u 1 −u 0 , v 1 =u 2 −u 1 , v 2 =u 3 −u 2 , ..., then we have a
sequence whose (k−1)-st order differences are constant. By induction,
we have a representation of the form
vn=bk− 1 nk−^1 +bk− 2 nk−^2 +···+b 1 n+b 0 ,for suitable constantsb 0 , b 1 , b 2 , ...,bk− 1.
Next — and this is the relatively difficult part — leta 1 , a 2 , ...,ak
be the unique solution of the linear equations represented in matrix
form:
Ä 1
1äÄ 2
2äÄ 3
3ä
···Äk− 1
k− 1äÄk
kä0
Ä 2
1äÄ 3
2ä
···Äk− 1
k− 2äÄ k
k− 1ä0 0
Ä 3
1ä
···Äk− 1
k− 3äÄ k
k− 2ä
... ... ...
Äk− 1
1äÄk
2ä0 0 0 ··· 0
Äk
1ä
a 1
a 2
a 3
...
ak
=
b 0
b 1
b 2
...
bk− 1
.
Having solved the above, one then verifies that the equation
ak(n+ 1)k+ak− 1 (n+ 1)k−^1 +···+a 1 (n+ 1)=aknk+ak− 1 nk−^1 +···+a 1 n+bk− 1 nk−^1 +bk− 2 nk−^2 +···b 1 n+b 0.(^26) As an alternative to using the theorem, note that if a sequence u= (un) has constantk-th
order differences, then, in fact,usatisfies thehomogeneousdifference equationC(u) = 0, where
C(x) = (x−1)k+1. One can now proceed along the lines of the “repeated factor” case, given above.