Consider the following recurrence relation defined only for n = 2 k for integers k such that k ? 1: T(2) = 7, and for n ? 4, T(n) = n + T(n / 2).[20] Consider the following recurrence relation defined only for n = 2* for integersk such that k 2 1: T(2) = 7, and for n 2 4, T(n) = n + T(n/2).Three students were working together in a study group and came up with thisanswer for this recurrence: T(n) = n * log, (n) – n – log2(n) + 8.Determine if this solution is correct by trying to prove it is correct by induction. Ifyou cannot complete the induction proof, explain what goes wrong.