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

 

Transcribed Image Text:

1. This question refers to the following recurrence relation. 1, T(n) = { } } (n - n = 0 3T (n-1)+2n, n 1 (a) [2 marks] Assume that n is much larger than 1. Use the recurrence relation to write T(n) in terms of T(n - 1), then in terms of T(n-2), then in terms of T(n-3). You can perform more substitutions if you wish in order to see the pattern. (b) [2 marks] Conjecture an expression for T(n) in terms of T(n - j), for an arbitrary j. Your expression can involve summation notation. For what range of j values does your conjecture apply? (c) [2 marks] Using part (b), conjecture a closed-form solution for T(n) as a function of n. Evaluate any summation notation. Here are two useful identities that hold for any n > 1 and any constant q, q> 0 and q 1. n-1 k=0 - q" - 1 1 n-1 kak nqn +1 n+1 1 = k=0 9-1 (9-1)2 (d) [3 marks] Prove your conjecture using mathematical induction. 1. This question refers to the following recurrence relation. 1, T(n) = { } } (n - n = 0 3T (n-1)+2n, n 1 (a) [2 marks] Assume that n is much larger than 1. Use the recurrence relation to write T(n) in terms of T(n - 1), then in terms of T(n-2), then in terms of T(n-3). You can perform more substitutions if you wish in order to see the pattern. (b) [2 marks] Conjecture an expression for T(n) in terms of T(n - j), for an arbitrary j. Your expression can involve summation notation. For what range of j values does your conjecture apply? (c) [2 marks] Using part (b), conjecture a closed-form solution for T(n) as a function of n. Evaluate any summation notation. Here are two useful identities that hold for any n > 1 and any constant q, q> 0 and q 1. n-1 k=0 - q" - 1 1 n-1 kak nqn +1 n+1 1 = k=0 9-1 (9-1)2 (d) [3 marks] Prove your conjecture using mathematical induction.