Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Here are some approaches technique 1 technique 2. – Mhenni Benghorbal Mar 20 '13 at 2:10

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.

share|cite|improve this answer
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$$

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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