Advanced High-School Mathematics

SECTION 2.1 Elementary Number Theory 97

Finally, one can show thatanysolution of (2.4) is of the form given

in (2.5). We won’t belabor these details any further.

Example 1.Solve the second-order linear homogeneous difference

equation

un+2 = un+1+ 2unn= 0, 1 , 2 ,...

given thatu 0 = 0 andu 1 = 1.

Solution. Note first that writing down the first few terms of the

sequence is easy:

u 2 = u 1 + 2u 0 = 1 + 0 = 1

u 3 = u 2 + 2u 1 = 1 + 2 = 3

u 4 = u 3 + 2u 2 = 3 + 2 = 5

u 5 = u 4 + 2u 3 = 5 + 6 = 11

and so on. In other words, the first few terms of the sequence look

like

un = 0, 1 , 1 , 3 , 5 , 1 , ....

What we’re trying to find, however, is a recipe for the general term.

Since the characteristic polynomial of this difference equation is

C(x) =x^2 −x−2 = (x+ 1)(x−2), we conclude by equation (2.5)

that the solution must look like

un = A 12 n+A 2 (−1)n, n= 0, 1 , 2 ,...

whereA 1 andA 2 are constants. However, sinceu 0 = 0 andu 1 = 1

we obtain