104 CHAPTER 2 Discrete Mathematics
Finally, we seta 0 =u 0 and use the fact that un+1=un+vn to check
that
un=aknk+ak− 1 nk−^1 +···+a 1 n+a 0 ,
and we are finished, as we have successfully proved that the terms of
the sequenceu 0 ,u 1 ,...,are expressible as a polynomial of degreek.
As for the converse, we assume that the sequenceu 0 ,u 1 ,u 2 ,...is be
expressible as a polynomial of degreekinn:
un=aknk+ak− 1 nk−^1 +···+a 1 n+a 0 ;we shall show by induction on k that the k-th order differences are
constant. To this end, let
Note next that the first order differences are
vn = un+1−un
= (ak(n+ 1)k+ak− 1 (n+ 1)k−^1 +···+a 0 )
−(aknk+ak− 1 nk−^1 +···+a 0 )
= polynomial innof degree at mostk− 1.By induction, the sequence (vn)n≥ 0 has constant (k−1)-st differences.
But then it follows immediately that the sequence (un)n≥ 0 must have
constantk-th order differences, and we are done!
Example 3. Solve the inhomogeneous linear difference equation
un+2− 2 un+1+un= 1, n= 0, 1 , 2 ,..., u 0 = 2, u 1 = 4.Solution. The difference equation says that the second-order differ-
ences are constant and equal to 1; this implies that the sequence must
be quadratic, say
un=an^2 +bn+c, n= 0, 1 , 2 ,....Note first that we can solve for the leading coefficientaby substituting
the polynomialan^2 +bn+cinto the above difference and noting that
the linear terms (bn+c) have zero second-order differences and hence
don’t contribute. This gives