Question

Find the closed form for each T(n given as a recurrence: 4 | T(m - 1) + 2 : n > 2 2 T(n) = T(n-1) + 4n -3 : : n=1 n> 1 1 2 n= 1 | 2T(n − 1)-1 : n> 2 T(m) = { 27 (m-1)+m-, : m=1 T(m) = 21 m - 1) + m : . m m -1 =1 > 1 5. Let n = 2m - 1. Rewrite your answer of the previous problem as a function of n.

Answer 1

1)

T(n) = T(n-1) + 2 = T(n-2) + 2*2 = ..... = T(n-n) + n*2 = T(0) + 2n = 2n + 2

2)

T(n) = T(n-1) + 4n-3 = T(n-2) + 4[n + (n-1)] - 3*2 = ..... = T(n-n) + 4[n + (n-1) + ...... + 1] - 3*n

=T(0) + 4 * n*(n+1)/2 - 3n

= 2 + 2n(n+1) - 3n

= 2 + 2n^2 + 2n - 3n

= 2n² - n + 2

NOTE: As per HOMEWORKLIB POLICY I am allowed to answer specific number of questions (including sub-parts) on a single post. Kindly post the remaining questions separately and I will try to answer them. Sorry for the inconvenience caused.