ABSTRACT
A difference equation is any definition of the general term in a sequence in terms of one or more previous terms and initial cases. Such a definition is also called a recurrence.
For example, in Section 1.5 we let hn be the minimum number of moves to solve n-ring Towers of Hanoi and showed that
hn+1 = 2hn + 1 for n ≥ 1, h1 = 1. This is a difference equation. It is a special case of the general linear difference equation
an = k∑
cian−i + f(n), a1, a2, . . . , an specified,
which is the topic of Sections 5.5 and 5.7. Here an is the general term of the unknown sequence, and the coefficients c1, . . . , ck and the function f(n) are known.
