Bonus exercise: recurrent equations (30 points). Consider the following particular type of recurrence: 1, aT(n/b) +ne, n>1 T(n)- where a 2 1 and b >1 are integers, and k log,n is integer (that is, we can only pick sizes n of the form where k2 0 is an integer). Use mathematical induction to prove that ne(1 log,n), if clog, a trilog.ne , fc*logba T(n) Hint: as a simpler example, see exercise 2.3-3. Consequently, prove the master theorem for this recurrence, that is, prove that (r), if c > logba