Advanced High-School Mathematics

96 CHAPTER 2 Discrete Mathematics

Quadratic—distinct factors over the reals. Next, assume that our

polynomialC(x) is quadratic; C(x) =x^2 −ax−b, where a, b∈

R. Thus, we are trying to solve the second-orderhomogeneous

difference equation

un+2=aun+1+bun, n= 0, 1 , 2 ,... (2.4)

Assume furthermore thatC(x) factors into twodistinctreal linear

factors:

C(x) = (x−k 1 )(x−k 2 ), k 16 =k 2 ∈R.

In this case it turns out that we bothun=kn 1 A 1 , n= 0, 1 , 2 ,...

andun = kn 2 A 2 , n = 0, 1 , 2 ,..., where A 1 , A 2 ∈ R are both so-

lutions of (2.4). This is verified by direct substitution: if un =

k 1 nA 1 , n= 0, 1 , 2 ,..., then

un+2−aun+1−bun = kn 1 +2A 1 −akn 1 +1A 1 −bk 1 nA 1

= kn 1 A 1 (k^21 −ak 1 −b)

= kn 1 A 1 (k 1 −k 1 )(k 1 −k 2 ) = 0.

This proves thatun=k 1 nA 1 , n= 0, 1 , 2 ,...is a solution. Likewise,

un = k 2 nA 2 , n = 0, 1 , 2 ,... is another solution. However, what

might seem surprising is that the sum

un = kn 1 A 1 +k 2 nA 2 , n= 0, 1 , 2 ,... (2.5)

of these solutions is also a solution of (2.4). Again, this is proved

by a direct substitution:

un+2 − aun+1− bun

= k 1 n+2A 1 +kn 2 +2A 2 −a(k 1 n+1A 1 +k 2 n+1A 2 )−b(k 1 nA 1 +kn 2 A 2 )

= kn 1 +2A 1 −ak 1 n+1A 1 −bk 1 nA 1 +kn 2 +2A 2 −akn 2 +1A 2 −bk 2 nA 2

= kn 1 A 1 (k 12 −ak 1 −b) +kn 2 A 2 (k 22 −ak 2 −b)

= kn 1 A 1 (k 1 −k 1 )(k 1 −k 2 ) +k 1 nA 2 (k 2 −k 1 )(k 2 −k 2 ) = 0 + 0 = 0.