2. This question refers to the following recurrence relation. 1, T(n) = 2. n = 0...

  

Transcribed Image Text:

2. This question refers to the following recurrence relation. 1, T(n) = 2. n = 0 n = 1 8T(n-2) 2", n2 (a) In parts (i) (iii), 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), then 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. 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. Recall that for any n1 and any constant q, q>0 and q 1, n-1 k=0 = q" - 1 9-1 (b) [2 marks] The closed form solution to this recurrence relation is T(n) = 2", Vn 0. Prove that this solution is correct using strong mathematical induction. Note that this formula holds for both even and odd n. A proof by cases is not necessary. 2. This question refers to the following recurrence relation. 1, T(n) = 2. n = 0 n = 1 8T(n-2) 2", n2 (a) In parts (i) (iii), 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), then 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. 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. Recall that for any n1 and any constant q, q>0 and q 1, n-1 k=0 = q" - 1 9-1 (b) [2 marks] The closed form solution to this recurrence relation is T(n) = 2", Vn 0. Prove that this solution is correct using strong mathematical induction. Note that this formula holds for both even and odd n. A proof by cases is not necessary.