1. Solve the recurrence exactly and prove your solution is correct by induction.
T(1) = 1 , T(n) = 2T(n-1)+2n-1
T(1) = 1, T(n) = T(n-1)+3n-3
2. Give asymptotic bound for the following:
T(n) = 9T(n/3)+n2
T(n) = T(Sqrt(n))+1.
A recurrence is solved and an asymptotic bound is found. The solution is detailed and well presented.