a) Given the recursively defined sequence. ar = 2x-1 + 2k, for all integers k > 2, a1 = 1 i) Find the first three terms. (2 marks) ii) Write the recursive algorithm. (5 marks) b) A certain computer algorithm executes twice as many operations when it is run with an input of size k as it is run with an input of size k-1 (where k is an integer that is greater than 1). When the algorithm is run with an input of size 1, it executes seven operations. Let rk = the number of executes with an input size k. Find a recurrence relation for ri, r2, .... Ik (4 marks) c) Given the recursive algorithm: Input: n Output: S(n) S(n) { if (n=1) return 5 return 5*S(n-1) } Trace S(4). (4 marks)