Given two functions f,g : R+ 7R,

1. f O(g(n)) if and only if c R+,n0 R0(n n0 (f(n) cg(n))).

2. f (g(n)) if and only if c R+,n0 R0(n n0 (f(n) cg(n))).

3. f (g(n)) if and only if O(g(n)) and (g(n)).

6. For this question, you are not allowed to use the known solution of what the sum of a geometric sequence is.

(a) Consider the inequality, for all n 2, given by n i=1 4/5^i < 1 /(couldnt use typeset, but starting is at i = 1 and ending at "n". 4/5^i < 1). Why would it be difficult to prove this using induction? .

(b) In order to prove the inequality in(a), prove the following stronger inequality, for all n 2, using induction instead. Show why proving this bound proves (a).

n i=1 4/5^i 11/5^n (Starting at i = 1, ending at "n". 4/5^i <= 1 - 1/5^n)