Answer Happy

2. This question refers to the following recurrence relation. 1, 3, 4T(n − 2) +2n, T(n) = n = 0 n = 1 n>1 (a) In the following questions, consider the case where n is even only. You do not need to repeat your calculation for the case where n is odd. (i) [2 marks] Assume that n is much larger than 1. Use the recurrence relation to write T(n) in terms of T(n − 2), then in terms of T(n − 4), and finally in terms of T(n-6). - (ii) [2 marks] Conjecture an expression for T(n) in terms of T(n − 2j), for an arbitrary j. (You may use summation notation, but your expression should be sufficiently simple that it is not needed.) For what range of j values does your conjecture apply?
(iii) [2 marks] Using part (ii), conjecture a closed-form solution for T(n) as a function of n. Evaluate any summation notation. (b) [3 marks] The closed form solution to this recurrence relation is T(n) = 2n + n2n-1, Vn > 0. Prove that this solution is correct using strong mathematical induction. Note that you do not need to separate the case where n is odd from the case where n is even.