## Linear recurrence equations

The general method for solving a recurrence equation of the form

with given, is rather simple to describe (in principle - in practice it may be quite hard).

First, guess'' , where and are constants. Substituting into the recursion relation and simplifying, we find that can be arbitrary but must satisfy

Let be the roots of this polynomial. We shall assume that these roots are distinct. Under these conditions, let be an arbitrary linear combination of all your guesses'',

Recall that are known, so we have equations in the unknown . This completely determines .

Example 1.7.20   Let satisfy and let .

We must solve , whose roots are and . Therefore,

Since and , we have

The recurrence equation

 (1.3)

is equivalent to the matrix equation

where is given as above. Let

Then the recursive equation is equivalent to . The sequence is periodic with period if and only if . The sequence is eventually periodic with period if and only if , for some .

Example 1.7.21   Define , , . The above method gives

david joyner 2008-04-20