102 CHAPTER 2 Discrete Mathematics
higher-order differences. The arithmetic sequences have con-
stant first-order differences; ifdis this difference then we haveun+1−
un=d, n= 0, 1 , 2 ,.... Suppose next that the second-order differences
are constant: this means that the difference of the difference is constant,
written as
(un+2−un+1)−(un+1−un) =d, n= 0, 1 , 2 ,....In other words,
un+2− 2 un+1+un=d, n= 0, 1 , 2 ,....Writing more compactly and in terms of the characteristic polynomial,
we have
C(u) =d, n= 0, 1 , 2 ,...,where C(x) = (x−1)^2 ,and wheredis the constant sequenced, d, ....
Constant third-order differences with constant differencedwould be
expressed as
((un+3−un+2)−(un+2−un+1))−((un+2−un+1)−(un+1−un)) =d, n= 0, 1 , 2 ,...,
i.e.,
un+3− 3 un+2+ 3un+1−un=d, n= 0, 1 , 2 ,....Again, a compact representation of this difference equation is
C(u) =d, n= 0, 1 , 2 ,...,where C(x) = (x−1)^3.Continuing along these lines we see that a sequence with finite k-th
order differences can be expressed via
C(u) =d, n= 0, 1 , 2 ,...,where C(x) = (x−1)k. (2.7)