5.1 Introduction

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 h _n be the minimum number of moves to solve n-ring Towers of Hanoi and showed that

This is a difference equation. It is a special case of the general linear difference equation

which is the topic of Sections 5.5 and 5.7. Here a _n is the general term of the unknown sequence, and the coefficients c ₁, , c _k and the function f(n) are known.

As another example, consider

This is nonlinear because max is a nonlinear function. It is a special type of solvable nonlinear recurrence that shows up in studying recursive algorithms; see Section 5.8. More typical of the behavior of nonlinear recurrences is the quadratic difference equation

which we study in Section 5.10.

Note that each but the last of the above examples consists of more than one equation. Technically speaking, the first equation in each display above is the difference equation and the rest is an initial condition or initial conditions, but we will often regard such pairs as a unit and refer to that unit as a difference equation. You need initial conditions to get a specific sequence as the solution. Otherwise, as in Eq. (1), you get...