Notes on Solving Linear Homogeneous Recurrences with Constant Coefficients
1) The Pattern for the General Solution
The following examples show the general form of the solution when given the
list of roots of the characteristic equation for each recurrence. These are not
complete problems, as the recurrence equation and initial conditions are not
shown. Of course, the final answer is not produced either, since we do not
have complete problems.
Roots of characteristic equation: General form of solution:
3, 2
=
4, -1, -1
=
2/3, 5, 5, 5
=
2, 2, 2, 2, -3, -3
=
2) Finding the roots of the characteristic equation
Sometimes the characteristic equation is difficult to solve. One method is to use
Mathematica to find the roots of the equation. If you need to solve by hand, the
Rational Root Theorem can be used to find any rational roots. (It will not directly
find any irrational roots, however).
Example:
=
The rational root theorem has you write down the factors of 9, namely 1, 3, 9
and the factors of 10, namely, 1, 2, 5, 10. The possible rational roots are then
the quotients formed by using each of the latter factors divided by each of the
former, with a + or - sign on each quotient. Thus, our example has the following
list of possible rational roots:
=
=
=
=
=
=
=
=
Now that we have the list of possible rational roots, we try them one by one in:
f(r) =
Since integers are easier to use than fractions, let's start with the integers:
Try 1:
f(1) =
=
so 1 is not a root
Try 2:
f(2) =
=
=
Thus 2 is a root of the characteristic equation and (r - 2) is a factor of f(r).
We therefore can use long division to get the quotient as follows. Note the
similarity to ordinary long division with plain numbers.
This is the quotient here on top.
---------------------------
|
|
-------------
-------------
-------------
No remainder, it divides evenly,
which we knew it had to do since r - 2
was known to be a factor.
Thus
f(r) =
=
Our quotient can be factored
by trial and error:
=
The characteristic equation thus factors to:
=
Thus we get:
=
or
=
or
=
=
=
=
=
=
These are the three roots to the characterstic equation.
3) Solving a system of linear equations:
Sometimes the initial conditions of a recurrence problem produce a system of
n linear equations in n variables. For example, the initial conditions in a certain
recurrence problem gives rise to this system of linear equations:
=
=
=
We can represent this as the matrix:
To solve the system of equations, our goal is to get 1's down the main diagonal
and 0's above and below these 1's. The rules which we can use to do this are:
a) We can interchange any two rows.
b) We can multiply any row by any nonzero constant.
c) We can add any multiple of a row to any other row.
First we try to get 0's below that 1 in the upper left corner of the matrix. We do
this by adding -2 times the first row to the second row and then adding -4 times
the first row to the last row. This gives the new matrix:
This matrix represents a system of equations that is equivalent to the original
system, that is, that has the same solutions.
Since we see that the last row has all negative signs and all multiples of 3, we
simplify by multiplying that row by -1/3. This gives:
Now we want to get a 1 in the second row, second column entry. We could
multiply the second row by 1/3, but we would get a fraction for the column 3
entry. Therefore, let's just interchange rows 2 and 3. This gives:
Next, we want to get 0's above and below that 1 in row 2, column 2. We do
this by adding -1 times the second row to the first row and then adding 3
times the second row to the last row. This gives:
Now we move to the third column. We want to get a 1 in row 3, column 3.
We do this by multiplying the last row by 1/2. This gives:
Above the 1 we just produced, we want to see all 0's. Well, the row 1,
column 3 entry is already a 0, so nothing has to be done there. The row 2,
column 3 entry is not 0. We fix that by adding -1 times the third row to row
2. This gives the following:
Finally, we can turn this back into equations and read off the answers for
A, B, and C:
=
=
=