Consider the following recurrence. For convenience, assume n is a power of 2. That is, n=2^k

T(n) = 1 if n = 1

T(n) = 2T(n/2) + 6n -1 if n > 1

(a) Solve the recurrence exactly by using repeated (or back) substitution.

(b) Prove using mathematical induction the correctness of the result you found in part(a).

Note: Your induction proof must consists of 3 components: the base case, an inductive hypothesis, and an inductive step. Furthermore, your inductive step must explicitly state where the inductive hypothesis is used.