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 Fol 1 (84.25 KiB) Viewed 58 times
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.
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!