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.
 A: 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.
A: 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$$
A: 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
$$
