Solving the recurrence relation $T(n)=2T(n/4)+\sqrt{n}$ I've solved $T(n)=2T(n/4)+\sqrt{n}$ to equal $2^{\log_{4}n}(\log_{4}n+1)$, but I'm not sure how to solve it directly.
I have:
$2(2T(\frac{n}{16})+\sqrt{\frac{n}{4}})+\sqrt{n} = 4T(\frac{n}{16})+2\sqrt{n}$
$2(4T(\frac{n}{64})+2\sqrt{\frac{n}{16}})+\sqrt{n} = 8T(\frac{n}{64})+2\sqrt{n}$
$2(8T(\frac{n}{256})+2\sqrt{\frac{n}{64}})+\sqrt{n}=16T(\frac{n}{256})+\frac{5}{4}\sqrt{n}$
I'm not seeing a pattern here and I'm not sure I'm modifying $n$ as necessary. What's the problem?

Let's turn the equation $T(n) = 2 T(n/4) + \sqrt{n}$ into a recurrence equation. To this end, let $f(m) = T(4^m p)$ for some $p>0$. Then
$$
     f(m) = 2 f(m-1) + \sqrt{p} 2^m
$$
which can be systematically solved. First rewrite it as
$$
     2^{-m} f(m) - 2^{-(m-1)} f(m-1) = \sqrt{p} 
$$
Then sum equations from $m=1$ to some upper bound $k$:
$$
 \sum_{m=1}^k \left(2^{-m} f(m) - 2^{-(m-1)} f(m-1) \right) = \sum_{k=1}^m \sqrt{p} 
$$
The sum on the left-hand-side telescopes:
$$\begin{eqnarray}
   \sum_{m=1}^k \left(2^{-m} f(m) - 2^{-(m-1)} f(m-1) \right) &=& \left(2^{-m} f(m) - \color\green{2^{-(m-1)} f(m-1)}\right) +  \\
  &\phantom{=}& \left(\color\green{2^{-(m-1)} f(m-1)} - 2^{-(m-2)} f(m-2)\right) + \\
  &\phantom{=}& \vdots \\
  &\phantom{=}& \left( 2^{-2} f(2) - \color\green{2^{-1} f(1)} \right) +\\ 
  &\phantom{=}& \left( \color\green{2^{-1} f(1)} - 2^{-0} f(0) \right) \\
  &=& 2^{-m} f(m) -  f(0)
\end{eqnarray}
$$
Hence we arrive at the solution
$$
   f(m) = 2^m \left( m \sqrt{p} + f(0) \right)
$$
since $m = \log_4 \left(\frac{n}{p}\right)$ we get:
$$
    T(n) = \sqrt{\frac{n}{p}} \left( \sqrt{p} \cdot \log_4 \frac{n}{p} + f(0)\right) = \sqrt{n} \log_4(n) + d \sqrt{n}
$$
where $d$ is a free constant to be determined by the initial condition.
