Notes on Second-Order Linear Homogeneous Recurrence Relations with Constant Coefficients
(Revised 8 July 2004)

It turns out that the behavior of a sequence defined by a SOLHRRCC an = Aan-1 + Ban-2 depends on the so-called characteristic equation

t2 - At - B = 0

This is just a plain old quadratic equation, and you learned how to solve them in your algebra course. You can use the quadratic formula from your algebra book to see that the solutions are

r1 = (A + Sqrt(A2 + 4B)/2

and

r2 = (A - Sqrt(A2 + 4B)/2
Now (A2 + 4B) may be positive or negative or zero, and so there are three different cases to deal with.
D = (A2 + 4B) is called the discriminant of the recurrence relation, because we use it to discriminate between the three cases. Here they are:

Case 1: D > 0

The formula for the n-th term is

an = E r1n + F r2n

and then it's just a matter of figuring out what the numbers E and F need to be. Epp shows examples of how this is done in Section 8.3; its the "two real roots" case.

Case 2: D = 0

In this case, r1 = r2 and there is only one solution of the characteristic equation. The formula for the n-th term in this case is

an = E rn + F n rn

where r = r1 = r2, and again it's a matter of figuring out what the numbers E and F are. Epp also shows examples of how this is done. It's the "one real root" case.

Case 3: D < 0

Epp does not treat this case. In fact, she doesn't even allude to its existence! You can see what the problem is: the quadratic formula tells you that you have to take the square root of a negative number! So, the solutions r1 and r2 are not real numbers!

Note that since D = A2 + 4B, the only way for D to be negative is for B to be negative (since A2 is never negative). B < 0 is a necessary (but not sufficient!) condition for D < 0.

Just for those of you who know about the trigonometric functions sine and cosine and tangent and their inverses: the formula for the n-th term in Case 3 is

an = Rn(E sin(K n) + F cos(K n))

where R = Sqrt(-B) and K = tan-1(Sqrt(-D)/A), and one has to find the appropriate values of E and F.

But don't worry about remembering those forms - if you run into a SOLHRRCC, you can go look this stuff up. What we'll do now is much more fun.

I've attached an Excel spreadsheet in which you can enter the coefficients A and B, and the first two terms a0 and a1. The spreadsheet computes the first 40 terms of the sequence and graphs them. It's the graphs that are interesting! The spreadsheet also computes the discriminant, determines the type of solution (Case 1, Case 2, or Case 3), and computes the roots of the characteristic equation when they are real numbers. In Case 3, the roots of the characteristic equation are not real numbers, but the spreadsheet computes the absolute value of the roots. (Its the same for both.)

The Discussion Question

Experiment with the spreadsheet by entering a variety of values for A, B, Term 0,and Term 1. See if you can identify any patterns. Write a paragraph (or several) describing what patterns you are seeing, and post it as a response to this main topic. Read some of your fellow students' postings, and respond to at least one, e.g. by comparing your fellow student's findings to yours, or with some other appropriate observation.