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

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

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

and

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

If is any other sequence satisfying

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

In general, this sort of argument proves the following.

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