The Big Question - Algorithmic Analysis III

Question

I have the following question:

Solve a recurrence relation that simplifies the answer using the Big 'O' notation:

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

I know that this is a first-order non-uniform recurrent order relation, and I have a question, but I can’t get the correct conclusion for the base case (f (0) = 2).

The question SHOULD use the sum of the geometric series of forumla in the proof.

Here is my answer - The sum of the notes (x = y, z) is a replacement for the sigma capital entry, where x is the lower limit of the summation, initialized by y, and z is the upper limit of the summation:

 1. *change forumla:* 2. f(n) = 6^ng(n) 3. => 6^ng(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 that the equation in line 11 can be simplified, and secondly, knocking at n = 0 should lead to result 2. I cannot get this answer, reaching line 13 ...

EDIT: I need to know why I don't get f (0) = 2 when substituting n = 0 in the equation on line 12. Also, I would like to know how I can simplify the equation for f (n) on line 12?

Anyone ...?

Answer 1

Without thinking about this, I will say that f (n + 1) is 6 times greater than f (n), minus a constant. f (n) therefore, of course, O (6 ^ n). Although you can find tougher attachment, as far as I would practice!

For fun, I will 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 will be afraid that

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

and I'm sure I can prove it by induction in several lines (the exercise remains as an exercise for the student).

Now,

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

so

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

confirming my earlier intuition.

Let's just do some quick checks:

 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 

This is enough for me for homework :-)