## Solving Second-Order Difference Equations with Constant Coefficients

Suppose you have a linear, homogeneous second-order difference equation with constant coefficients of the form $a_{n+2} = A a_{n+1} + B a_n$.  The solution procedure is as follows: “Guess” a solution of the form $a_n = r^n$.  Then substitute this guess into the difference equation to obtain $r^{n+2} = A r^{n+1} + Br^n$.  Divide both sides by $r^n$ (assuming $r \neq 0$), yielding $r^2 = Ar + B$.  Solve this equation to obtain the two solutions $r = r_1$ and $r = r_2$.  This gives two solutions to the original difference equation: $a_n = r_1^n$ and $a_n = r_2^n$.  Assuming $r_1 \neq r_2$, 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 $r_1^n$ and $r_2^n$, which means that the general solution to $a_{n+2} = A a_{n+1} + B a_n$ is $a_n = C r_1^n + D r_2^n$, where C and D are determined by the initial conditions $a_0$ and $a_1$.

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 $a_n = C r_1^n + D r_2^n$ is actually the correction solution (with no guesses!).

The derivation uses generating functions.  We’ll start by reindexing the original recurrence into the form $a_n = A a_{n-1} + B a_{n-2}$.  Then multiply this equation by $x^n$ and then sum as n goes from 2 to infinity to obtain

$\displaystyle \sum_{n=2}^{\infty} a_n x^n = A \sum_{n=2}^{\infty} a_{n-1} x^n + B \sum_{n=2}^{\infty} a_{n-2} x^n$.

We want to reindex this equation so that each summation has the same bounds and the same subscripts for $a_n$.  Doing this yields

$\displaystyle \sum_{n=0}^{\infty} a_n x^n - a_0 - a_1 x= A \sum_{n=1}^{\infty} a_n x^{n+1} + B \sum_{n=0}^{\infty} a_n x^{n+2},$ or

$\displaystyle \sum_{n=0}^{\infty} a_n x^n - a_0 - a_1 x= A x \sum_{n=0}^{\infty} a_n x^n - a_0 x + B x^2 \sum_{n=0}^{\infty} a_n x^n$.

For simplicity’s sake, let’s let $\displaystyle S = \sum_{n=0}^{\infty} a_n x^n$.  This substitution and some rearrangement produces

$\displaystyle S - Ax S - Bx^2 S = a_0 + a_1 x - a_0 x$, which implies

$\displaystyle S = \frac{a_0 + (a_1 - a_0)x}{1 - Ax - Bx^2}$.

Now, let’s factor the denominator.  We already know that $x^2 - Ax - B = (x-r_1)(x-r_2)$.  Replacing x with $1/x$ produces $1/x^2 - A/x - B = (1/x-r_1)(1/x-r_2)$.  Then multiply by $x^2$ to obtain $1 - Ax - Bx^2 = (1-r_1 x)(1 - r_2 x)$.  Therefore,

$\displaystyle S = \frac{a_0 + (a_1 - a_0)x}{(1-r_1 x)(1-r_2 x)}$.

Applying partial fractions decomposition, we can write this as

$\displaystyle S = \frac{C}{1-r_1 x} + \frac{D}{1-r_2 x}$,

for some constants and D.  We could figure out what C and D are in terms of $a_0$ and $a_1$, 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

$\displaystyle S = C \sum_{n=0}^{\infty} (r_1 x)^n + D \sum_{n=0}^{\infty} (r_2 x)^n = \sum_{n=0}^{\infty} (C r_1^n + D r_2^n)x^n.$

Remembering that $\displaystyle S = \sum_{n=0}^{\infty} a_n x^n$, we now have

$\displaystyle \sum_{n=0}^{\infty} a_n x^n = \sum_{n=0}^{\infty} (C r_1^n + D r_2^n)x^n.$

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

$a_n = C r_1^n + D r_2^n$.

Remember, this is for the case when the characteristic polynomial $r^2 - Ar - B$ has two distinct roots $r_1$ and $r_2$.  Next month we’ll take a look at the repeated root case, where $r_1 = r_2$.