3. Give the closed-form solution of the recurrence relation where indicated by algebraically unrolling it or give the specified terms of the sequence denoted by the relation. (a) Solve T(n) 2T(n 1)2 with the initial condition T(1) 1. [10 points] (b) Give the first five terms, T(1), T(2),T(5), of the sequence denoted by the recur- rence relation in 4(a). [5 points] (c) Solve T(n) = 2T() + n with the initial condition T(1) = 1 where n is a nonnegative power of 3. [10 points] 4. Assume each function in the assertions below are from Z+ to R+. Prove that the propo sition is true, using the definition of the asymptotic notation(s) or disprove it by giving a counter-example and explaining how the counter-example disproves the assertion (a) Proposition 1: If fi(n) E O(gi(n)), f2(n) EO(g2(n)) and gi(n) E 0(92(n)) then fi(n)+f2(n) E O(92(n)). [15 points (b) Proposition 2: fi(n) E O(g(n)) and f2(n) E O(g(n)), then fi(n) E (f2(n). 10 points]