5.5 Constant Coefficient Homogeneous Linear Difference Equations

In this section, difference equation (or recurrence) means constant coefficient homogeneous linear difference equation (CCHLDE). We will show how to solve all such difference equations. That is, for each such recurrence, we will show how to find all sequences which satisfy it. We develop the solution method through examples and then summarize it as Theorem 2. Almost all our examples will involve second-order equations; such problems exhibit all the issues that arise in solving the general case.

In a final subsection, we briefly introduce an alternative solution method using generating functions.

To get an idea of what the solutions should look like, it is best to start with the simplest case, the general first-order CCHLDE,

We know the general solution is a _n =ar ⁿ, where a= a ₀. (See Example 1, Section 5.2, and also [3].) Eq. (1) is not the only difference equation we have met thus far with geometric growth. We saw that the Fibonacci numbers, which satisfy a second-order equation, grow with a ratio closer and closer to geometric as n increases. Also, the difference equation in [3, Section 5.3] was second order, but some of the solutions were exactly geometric. Let s guess, therefore, that every difference equation (linear, homogeneous, constant coefficient) has a geometric solution. If this turns out to be correct, then we ll worry about combining geometric solutions to get other solutions.

Example 1

Find all geometric solutions to

This difference equation...