next up previous
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 $ \{a_n\}$ satisfying $ a_0=0$, and

$\displaystyle a_{n+1}-2a_n = F_n$   for $ n \ge 0$$\displaystyle ,$ (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

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


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

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

$\displaystyle 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

$\displaystyle 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

$\displaystyle 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

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

or more simply,

$\displaystyle 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

$\displaystyle 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

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

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