Solving recurrence relations using substitution followed by tree method/masters theorem
For your first method, it is dominated by the first term, not the last.  (The second term is $2^{k/2} * 4 = 2^{(k/2)+2} &lt; 2^k$ for $k$ large.)

In your second method, when you divide each term by $2^k$, you didn't.  You divided the second term by $2^{(k/2)+1}$ instead.