Big O Question - Algorithmic Analysis III

Question

I have the following question:

Solve the recurrence relation simplifying the answer using Big 'O' notation:

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

I know this is a first order inhomogenous recurrence relation and have had a go at the question but I cannot seem to get the right output for the base case (f(0) = 2).

The question MUST use the sum of geometric series forumla within the proof.

Here is my answer - Note sum(x = y, z) is a replacement for capital sigma notation, where x is the lower bound of the summation initialised to y and z is the upper bound of the summation:

1.  *change forumla:*
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*

Firstly, I am sure the equation on line 11 can be simplified further and secondly subbing in n = 0 should yield 2 as the result. I cannot obtain this answer when reaching line 13...

EDIT: What I need to know is why I am not getting f(0) = 2 when subbing n = 0 into the equation in line 12. Also what I would like to know is how can I simplify the equation for f(n) in line 12?

Anyone...?

Answer 1

Without thinking too hard about this, I'm going to say that f(n + 1) is 6 times larger than f(n), minus a constant. f(n) is therefore certainly O(6^n). Although you may find a tighter bound, that's about as far as I'd go in practice!

For the fun of it, I'll try this:

f(1) = 6f(0) - 5
     = 6^1.f(0)
f(2) = 6f(1) - 5
     = 6(6f(0) - 5) - 5
     = 6^2.f(0) - 6^1.5 - 5
f(3) = 6f(2) - 5
     = 6^3.f(0) - 6^2.5 - 6^1.5 - 5

I'll hazard a guess that

f(n) = 6^n.f(0) - 5.(6^0 + 6^1 + ... + 6^(n-1))

and I'm pretty sure that I could prove this by induction in a few lines (exercise left as an exercise for the student).

Now,

sum (k in 0..n-1) 6^k  =  (1 - 6^n) / (1 - 6)

therefore

f(n) = 6^n.f(0) - 5.(1 - 6^n) / (1 - 6)
     = 6^n.f(0) + (1 - 6^n)
     = 6^n.(2 - 1) + 1
     = 6^n + 1

confirming my earlier intuition.

Let's just do a few quick check calculations:

f(0) = 2 = 6^0 + 1
f(1) = 6.2 - 5 = 7 = 6^1 + 1
f(2) = 6.7 - 5 = 37 = 6^2 + 1
f(3) = 6.37 - 5 = 237 = 6^3 + 1

That's enough for me for homework :-)