# non homogeneous recurrence relation

I am trying to solve the non-homogeneous linear recurrence relation:

$$f(n) = 6f(n-1) - 5,\quad f(0) = 2.$$

How do I go about doing it? This is so different from solving a homogeneous recurrence relation.

This answer shows one elementary method of solving exactly this kind of problem. There are many others, most of them considerably more general; this link gives an brief introduction to some of them. This PDF goes into considerably more detail.

• You didn't link "This PDF". – Gerry Myerson Mar 20 '13 at 1:49
• @Gerry: Thanks. (The link was there, but I lifted it from the Google returns, so it was missing the http://.) – Brian M. Scott Mar 20 '13 at 1:50

Split the solution into a homogeneous solution $f_n^{(H)}$ and inhomogeneous solution $f_n^{(I)}$. $f_n^{(H)}$ satisfies

$$f_n^{(H)} - 6 f_{n-1}^{(H)} = 0 \implies f_n^{(H)} = A\cdot 6^n$$

$f_n^{(I)}$ is found by a guess; in this case, we can guess that it is a constant, which we find to be $1$ by plugging an unknown constant into the recurrence relation. Therefore

$$f_n = A\cdot 6^n + 1$$

We find that $f_0=2 \implies A=1$. Therefore

$$f_n = 6^n + 1$$

If you like generating functions, define $F(z) = \sum_{n \ge 0} f(n) z^n$, write the recurrence with no subtractions in indices: $$f(n + 1) = 6 f(n) - 5$$ multiply by $z^n$, sum over $n \ge 0$, and recognize the sums: $$\frac{F(z) - f(0)}{z} = 6 F(z) - 5 \frac{1}{1 - z}$$ Now it is smooth sailing, get partial fractions: $$F(z) = \frac{1}{1 - 6 z} + \frac{1}{1 - z}$$ and expand as geometric series: $$f(n) = 6^n + 1$$