SECTION 2.1 Elementary Number Theory 107
- Solve the inhomogeneous linear difference equation
un+3− 3 un+2+ 3un+1−un= 2, n= 0, 1 , 2 ,...,u 0 = 0, u 1 = 4, u 2 = 10, u 3 = 20.- Given the sequenceu 0 ,u 1 ,u 2 ,..., note that the first fewk-th order
differences are
first-order: un−un− 1
second-order: (un−un− 1 )−(un− 1 −un− 2 ) =un− 2 un− 1 +un− 2
third-order: ((un−un− 1 )−(un− 1 −un− 2 ))−((un− 1 −un− 2 )−(un− 2 −
un− 3 ))
=un− 3 un− 1 + 3un+2−un− 3Find a general formula for thek-order differences and prove this
formula.- As we have seen, the sequence un = nk has constant k-th order
differences. Therefore,
∑k
l=0Ñ
k
lé
(−1)lun−l=∑k
l=0Ñ
k
lé
(−1)l(n−l)k= constant,i.e., is independent ofn.(a) Conclude from this that one has the curious combinatorial
identity: ifr < k, then∑k
l=0Ñ
k
lé
(−1)llr = 0.(Hint: Show that for each suchr the above expression is the
coefficient ofnk−r in the constant polynomial
∑k
l=0Ñ
k
lé
(−1)l(n−l)k.)