Next: The Mahler-Lech theorem Up: Linear recursive sequences Previous: Example: finding a linear

# Inhomogeneous recurrence relations

Suppose we wanted an explicit formula for a sequence satisfying , and

 for (8)

where is the Fibonacci sequence as usual. This is not a linear recurrence in the sense we have been talking about (because of the on the right hand side instead of 0), so our usual method does not work. A recurrence of this type, linear except for a function of on the right hand side, is called an inhomogeneous recurrence.

We can solve inhomogeneous recurrences explicitly when the right hand side is itself a linear recursive sequence. In our example, also satisfies

 (9)

and

 (10)

Subtracting (8) and (9) from (10) yields

Thus is a linear recursive sequence after all! The characteristic polynomial of this new linear recurrence is , so by Theorem 1, there exist constants such that

for all . Now we can use , and the values and obtained from (8) to determine . After some work, one finds , , and , so

If is any other sequence satisfying

 (11)

but not necessarily , then subtracting (8) from (11) shows that the sequence defined by satisfies for all , so for some number . Hence the general solution of (11) has the form

or more simply,

where is some constant.

In general, this sort of argument proves the following.

Theorem 3   Let be a linear recursive sequence satisfying a recurrence with characteristic polynomial . Let be a polynomial. Then every solution to the inhomogeneous recurrence

 (12)

also satisfies a linear recurrence with characteristic polynomial .

Moreover, if is one particular solution to (12), then all solutions have the form , where ranges over the solutions of the linear recurrence

Next: The Mahler-Lech theorem Up: Linear recursive sequences Previous: Example: finding a linear
Zvezdelina Stankova-Frenkel 2000-09-20