Suppose you have a linear, homogeneous second-order difference equation with constant coefficients of the form . The solution procedure is as follows: “Guess” a solution of the form . Then substitute this guess into the difference equation to obtain . Divide both sides by (assuming ), yielding . Solve this equation to obtain the two solutions and . This gives two solutions to the original difference equation: and . Assuming , and after arguing that the solutions to the original equation form a vector space of dimension 2 (we’ll leave that aside for now), your two solutions to the original equation form a basis for the solution space. This means that all solutions to the difference equation can be represented as a linear combination of the two basis solutions and , which means that the general solution to is , where C and D are determined by the initial conditions and .
Many of my students do not find this argument satisfying (although it is valid). They don’t like the guessing aspect near the beginning. How do you know the right guess? How would you come up with that guess? In this post we’ll do a direct derivation that is actually the correction solution (with no guesses!).
The derivation uses generating functions. We’ll start by reindexing the original recurrence into the form . Then multiply this equation by and then sum as n goes from 2 to infinity to obtain
We want to reindex this equation so that each summation has the same bounds and the same subscripts for . Doing this yields
For simplicity’s sake, let’s let . This substitution and some rearrangement produces
, which implies
Now, let’s factor the denominator. We already know that . Replacing x with produces . Then multiply by to obtain . Therefore,
Applying partial fractions decomposition, we can write this as
for some constants C and D. We could figure out what C and D are in terms of and , but for the purposes of this derivation we don’t need to do that.
Now we’re going to pull a property of generating functions. They can be thought of as formal power series, with the consequence that you can expand them as power series without worrying about questions of convergence. (See, for example, Wilf’s text generatingfunctionology.) Applying the geometric series expansion, we have
Remembering that , we now have
Since the only way two formal power series can be equal is if their coefficients are equal, we get the solution to the original difference equation to be
Remember, this is for the case when the characteristic polynomial has two distinct roots and . Next month we’ll take a look at the repeated root case, where .