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.

Hi I am revising for my exams and I have the following inhomogeneous first order recurrence relation defined as follows:

f(0) = 2
f(n) = 6f(n-1) - 5, n > 0

I have tried for ages using the methods I have been taught to solve this but I cannot get a proper solution.

1.  Integrate a new function g(n)
2.     f(n) = 6^n.g(n)
3.  => 6^n.g(n) = 6.6^(n-1) .g(n-1) -5   
4.  => g(n) = g(n-1)-5/6^n
5.  => g(n) = sum(i=1, n)-5/6^i
6.  => f(n) = 6^n.sum(i=1, n)-5/6^i
7.  => *Evaluate the sum using geometric series forumla*
8.  => sum(i = 1, n)-5/6^i = [sum(i = 1, n)a^i] -------> (a = -5/6)
9.  => *sub a = -5/6 into geometric forumla [a(1-a^n)/(1-a)]*
10. => [(-5/6(1 - (-5/6)^n))/(1-(-5/6))]
11. => g(n) = [(-5/6(1 + (5/6)^n))/(1+5/6)]
12. => f(n) = 6^n . g(n) = 6^n[(-5/6(1 + (5/6)^n))/(1+5/6)]
13. => *sub in n = 0 to see if f(0) = 2*

I cannot get this working, however. f(0) [base case] doesn't equal 2...Where have I gone wrong??

Just to let you know here is the example I am following:

f(0) = 0
f(n) = 3f(n-1)+1, n>0

f(n) = 3^n.g(n)
3^n.g(n) = g(n-1)+(1/3)^n
g(n) = sum(i=1, n)(1/3)^i
f(n) = 3^n . sum(i=1, n)(1/3)^n
sum(i=1, n) = sum(i=1, n)(a^i) ----> a = 1/3
sub into geometric series formula gives:

1/2(1-(1/3^n)

Hence:
f(n) = 3^n/2(1-(1/3^n)) = 1/2(3^n - 1) = O(3^n)

Now my maths isn't great, I know enough to get about but I have followed the exact steps as my lecturer did in the example, but I cannot get a solution to fit f(0). I have to follow the methods used in above example and I am absolutely stumped as to where the issue is..

share|improve this question
3  
btw +1 for showing your work. –  Aryabhata Apr 12 '11 at 19:41
    
@user: $\sum_{i=1}^{n} -5/6^i $ is not the same as $\sum_{i=1}^{n} (-5/6)^i$. –  Aryabhata Apr 12 '11 at 20:48
add comment

1 Answer 1

up vote 6 down vote accepted

Your step 5 is wrong.

We actually have

$$g(n) - g(0) = \sum _{j=1}^{n} \frac{-5}{6^j}$$

You missed the $g(0)$.

Thus giving us $g(n) = 2 - \frac{5(1 - (1/6)^n)}{6(1 - 1/6)} = 2 - \frac{6^n -1}{6^n} = 1 + 1/6^n$

Hence $f(n) = 6^n g(n) = 6^n + 1$.

A simpler way to approach this problem is to set $f(n) = h(n) + 1$

Which gives us $h(n) = 6h(n-1)$ and $h(0) = 1$.

Thus $h(n) = 6^n$ and so $f(n) = 6^n + 1$.

share|improve this answer
    
you're right, thanks for that - what repercussion does that have on the subsequent steps? I mean, it would still yield 'a' as (-5/6) to be subbed into the geometric series formula...Problem is -5/6 doesn't work.. –  user9492 Apr 12 '11 at 19:17
    
@User: The geometric series ratio is not $-5/6$. So yes, that is another problem. If it were $-5/6$, then the terms would be alternately positive and negative. In this case all terms are negative. –  Aryabhata Apr 12 '11 at 19:24
    
Wow your way is much easier, the only problem is I have to do it my way as I believe the exam is marked in such a way that you to show the individual steps applying methods taught during the lecture. I just don't get how to get where I am going wrong... –  user9492 Apr 12 '11 at 19:26
    
@user: Your other mistake is that the common ratio is not $-5/6$ (I edited my previous comment). –  Aryabhata Apr 12 '11 at 19:27
1  
@user: In this case, the series is $ar, ar^2, ar^3, \dots$ with $a = -5$ and $r = 1/6$. The common ratio is not $-5/6$. One hint to that is that the terms don't alternate between positive and negative, which they would if the common ratio was $-5/6$. Also, $5$ always appears as a $5$, not $5^2$, $5^3$ etc. –  Aryabhata Apr 12 '11 at 19:37
show 11 more comments

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.