Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
Here are some approaches technique 1 technique 2. –  Mhenni Benghorbal Mar 20 '13 at 2:10
add comment

3 Answers 3

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|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
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.