Take the following recurrence relation consider only for n = 2k for integers
k ≥ 1: T(2) = 9, and for n ≥ 4, T(n) = n + T(n /2).
Three students were working together in a study group and came up with three dissimi laranswers for this recurrence:
(a) T(n) = n log2(n) + 5
(b) T(n) = n log2(n) - n + 9
(c) T(n) = 2 n + 5
Examine which solution (if any) is correct by trying to prove that each one is correct by induction. If you cannot done the induction proof, describe what goes wrong.