7
$\begingroup$

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

  • 3
    btw +1 for showing your work.2011-04-12
  • 0
    @user: $\sum_{i=1}^{n} -5/6^i $ is not the same as $\sum_{i=1}^{n} (-5/6)^i$.2011-04-12

1 Answers 1

7

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

  • 0
    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..2011-04-12
  • 0
    @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.2011-04-12
  • 0
    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...2011-04-12
  • 0
    @user: Your other mistake is that the common ratio is not $-5/6$ (I edited my previous comment).2011-04-12
  • 0
    @Moron - Is it not? I am sure I have done it correctly...Could you tell me where I am going wrong with my calculations?2011-04-12
  • 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.2011-04-12
  • 0
    The equation I am using doesn't have a common ratio. It uses just 'a'. The formula I am told to use is a(1-a^n)/(1-a). I found 'a' to be -5/6...2011-04-12
  • 0
    @user: That seems to be the formula for $ a + a^2 + a^3 ...$ That is not the case here. What you have here is $-5(a + a^2 + ...)$ and not $(-5a) + (-5a)^2 + ...$ as you seem to think.2011-04-12
  • 0
    ok great - sorry to keep asking, i am still not quite sure how you got the definition g(n)=2−5(1−(1/6)n)6(1−1/6)=2−6n−16n=1+1/6n...Can you explain how you go from g(n)-g(0) =.... to the next line g(n) = ...2011-04-12
  • 0
    @user: $\sum_{j=1}^{n} \frac{-5}{6^j} = \frac{-5}{6} \sum_{j=0}^{n-1} (\frac{1}{6})^j = \dots$2011-04-12
  • 0
    where does the '2-...' come from? From f(0)? If so why are you subbing this value for g(n)...2011-04-13
  • 0
    @user: $g(n) = g(0) - \sum 5/6^j$ and $g(0) = 2$.2011-04-13
  • 0
    can you please explain how sum(i=1, n)-5/6^n = 5(1−(1/6)n)/6(1−1/6)? I'm completely confused now. The formula given is a(1-a^n)/(1-a) - therefore a = -5/6???? That is what happens in the example above, where a = 1/3...2011-04-13
  • 0
    @user: $\sum_{i=1}^{n} -5/6^i = -5 \sum_{i=1}^{n} 1/6^i = -5 \frac{(1/6 (1-1/6^n)}{(1-1/6)}$ Note that the -5 is outside and is not part of the $a$2011-04-13
  • 0
    sorry my comments dont seem to display- i understand your solution in the above comment but does this not differ to the one you offered in your answer above?2011-04-13
  • 0
    @user: I don't see how. I just moved the 6 from the 1/6 in the numerator to the denominator...2011-04-13