Reccurence Relation (Master Theorem) I have solution but break it down step by step/ line by line

Let T(1)-2, T(n) = 4T(n/2) + 2n for n > 1 Using the methods shown in class, find a closed-form formula for T(n). [lf you recall the Master Theorem, you may use it to predict the general form of your answer, but you must still then derive the exact formula.] a. b. Verify your formula for the case n2 To solve the recurrence, assume n = 2k and k = lg n Use a domain transformation, S(k) = T(n) = 4T(n/2) + 2n 4S(k-1) + 2.2k, s(0) = T(1) = 2 Use a range transformation, R(k) = S(k)/4" = 1/4" x (4 S(k-1) + 2-2k-R(k-1) + (2-29/4r_ R(k-1) + 2(112)" Using telescoping-adding up the equations _ we get R(k)-R(0)-2(1/2JE-0..k-1 (1/2)' = [(1/2)k-1] / [1/2-11-2-2(1/2)k R(k) 2 2 - 2(1/2) 4 21/2) T(n)- 4n2- 2n T(2) = 4x22-2x2-16-4 12, same as T(2) = 4T(2/2) + 2(2) = 4x2 + 4-12