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?