1. Consider the following recurrence equation, defining T(n), as T(n) - lr(n -1+2 otherwise Show, by induction, that T(n) 2n 2. Draw the recursion tree and use it to determine the solution for the following recurrence: 3. Solve the following recurrence: T) 3(er Ign) 5. 6. 7, Solve the following recurrence: T(n)-T () + ?(n3) Solve the following recurrence:t(n):I()+8(?) Solve the following recurrence: T(n) 2T(Vn])+Ign Show that the solution for T(n) = T(n-1) + n is 0(n2)