# Algorithmic Analysis Simplified under Big O

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

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