Advanced High-School Mathematics

94 CHAPTER 2 Discrete Mathematics

For certain values of k, the above sequence can exhibit some very
strange—even chaotic—behavior!

Thegeneral homogeneous linear difference equationoforder
khas the form

un+k=a 1 un+k− 1 +a 2 un+k− 2 +···+akun, n= 0, 1 , 2 ,...

Of fundamental importance is the associatedcharacteristic polyno-
mial

C(x) =xk−a 1 xk−^1 −a 2 xk−^2 −···−ak.

The charasteristic equation finds the zeros of the characteristic
polynomial:

xk−a 1 xk−^1 −a 2 xk−^2 −···−ak= 0.

Given the monic^23 polynomial

C(x) = xk−a 1 xk−^1 −a 2 xk−^2 −···−ak,

with real coefficients, and ifu= (un) is a sequence, we shall denote by
C(u) the sequenceu′= (u′n)n≥ 0 where

u′n = un+k−a 1 un+k− 1 −a 2 un+k− 2 −···−akun.

Therefore, the task of solving a linear difference equation is to solve

C(u) =v,

wherev= (vn)n≥ 0 is a given sequence. Ifv= 0 (the sequence all of
whose terms are 0) we call the difference equationhomogeneous. We
shall be primarily concerned with homogeneous difference equations;

(^23) “Monic” simply means that the leading coefficient is 1.