2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

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

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.