Inhomogeneous recurrence relations

Suppose we wanted an explicit formula for a sequence $\{a_n\}$ satisfying $a_0=0$, and

$$a_{n+1}-2a_n = F_n n \ge 0 ,$$ (8)

where $\{F_n\}$ is the Fibonacci sequence as usual. This is not a linear recurrence in the sense we have been talking about (because of the $F_n$ 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 $n$ 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, $\{a_n\}$ also satisfies

$$a_{n+2}-2a_{n+1} = F_{n+1}$$ (9)

and

$$a_{n+3}-2a_{n+2} = F_{n+2}.$$ (10)

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

$$a_{n+3}-3a_{n+2}+a_{n+1}+2a_n = F_{n+2}-F_{n+1}-F_n = 0.$$

Thus $\{a_n\}$ is a linear recursive sequence after all! The characteristic polynomial of this new linear recurrence is $x^3-3x^2+x+2=(x-2)(x^2-x-1)$, so by Theorem 1, there exist constants $A,B,C$ such that

$$a_n=A \cdot 2^n + B \alpha^n + C \beta^n$$

for all $n$. Now we can use $a_0=0$, and the values $a_1=0$ and $a_2=1$ obtained from (8) to determine $A,B,C$. After some work, one finds $A=1$, $B=-\alpha^2/(\alpha-\beta)$, and $C=\beta^2/(\alpha-\beta)$, so $a_n = 2^n - F_{n+2}.$

If $\{x_n\}$ is any other sequence satisfying

$$x_{n+1}-2x_n = F_n$$ (11)

but not necessarily $x_0=0$, then subtracting (8) from (11) shows that the sequence $\{y_n\}$ defined by $y_n=x_n-a_n$ satisfies $y_{n+1}-2y_n=0$ for all $n$, so $y_n=D \cdot 2^n$ for some number $D$. Hence the general solution of (11) has the form

$$x_n = 2^n - F_{n+2} + D \cdot 2^n,$$

or more simply,

$$x_n = E \cdot 2^n - F_{n+2},$$

where $E$ is some constant.

In general, this sort of argument proves the following.

Theorem 3   Let $\{b_n\}$ be a linear recursive sequence satisfying a recurrence with characteristic polynomial $f(x)$. Let $g(x)=c_k x^k + c_{k-1} x^{k-1} + \cdots + c_1 x + c_0$ be a polynomial. Then every solution $\{x_n\}$ to the inhomogeneous recurrence

$$c_k x_{n+k} + c_{k-1} x_{n+k-1} + \cdots + c_1 x_{n+1} + c_0 x_n = b_n$$ (12)

also satisfies a linear recurrence with characteristic polynomial $f(x)g(x)$.

Moreover, if $\{x_n\}=\{a_n\}$ is one particular solution to (12), then all solutions have the form $x_n = a_n + y_n$, where $\{y_n\}$ ranges over the solutions of the linear recurrence

$$c_k y_{n+k} + c_{k-1} y_{n+k-1} + \cdots + c_1 y_{n+1} + c_0 y_n = 0.$$