Solving $T(n)= 2T(n/2) + \sqrt{n}$ without master theorem (algebraically & recurrence tree) $$T(n)= 2T(n/2) + \sqrt{n}$$
This recurrence was in a stackoverflow question, and I want to solve it without relying on the master method. The solution was given, but wolframAlpha gives a slightly different equation:
$$(1) \quad T(n)= n/2 + (1+\sqrt2)(n-\sqrt{n})$$
My Attempt
This was an image that one of the replier's had:

From the recursion tree, I get that the recursion is $\sqrt{n} + 2\sqrt{n/2} + 4\sqrt{n/4} +...$
Reduced it becomes  $\sqrt{n} + \sqrt{2n} + \sqrt{4n} +...$
I'm pretty sure this summation happens log(n) times, which would make the equation be:
$$(2) \quad T(n)= \sum_{k=0}^{log(n)} \sqrt{2^kn}$$
Now I have no idea. I don't know how to solve a sum with log(n) bounds or if this is even set up right. How do I get from #2 to #1?
 A: There  is another  closely  related recurrence  that  admits an  exact
solution.  Suppose we  have  $T(0)=0$  and for  $n\ge  1$ (this  gives
$T(1)=1$)
$$T(n) = 2 T(\lfloor n/2 \rfloor) + \lfloor \sqrt{n} \rfloor.$$
These would seem to be reasonable assumptions since the work step of a recursive algorithm involves a discrete number of operations, i.e. an integer.
Furthermore let the base two representation of $n$ be
$$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$
Then  we can  unroll the  recurrence to  obtain the  following exact
formula for $n\ge 1$
$$T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
2^j\Bigg\lfloor
\sqrt{\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}}
\Bigg\rfloor.$$
Now to get an upper bound consider a string of digits with value one
to obtain
$$T(n) \le \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
2^j \sqrt{\sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^{k-j}}
= \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
2^j \sqrt{2^{\lfloor \log_2 n \rfloor +1 - j} -1}
\\ < \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
\sqrt{2}^{2j} \sqrt{2^{\lfloor \log_2 n \rfloor +1 - j}}
= \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
\sqrt{2}^{\lfloor \log_2 n \rfloor +1+j}
\\ = \frac{\sqrt{2}^{\lfloor \log_2 n \rfloor +1}-1}{\sqrt{2}-1}
\sqrt{2}^{\lfloor \log_2 n \rfloor +1}.$$
Note that  this bound suffers  from a defect  namely that when  $j$ is
close to $\lfloor \log_2 n \rfloor$ in the second sum the error, which
is  comparatively  large,  gets   magnified  by  a  factor  of  $2^j.$
Nonetheless it suffices for the asymptotics.

This bound is actually attained and cannot be improved upon, just like
the lower bound,  which occurs with a one digit  followed by zeroes to
give
$$T(n) \ge \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
2^j \left(\sqrt{2^{\lfloor \log_2 n \rfloor-j}} -1 \right)
= - \left(2^{\lfloor \log_2 n \rfloor+1} - 1\right) +
\sum_{j=0}^{\lfloor \log_2 n \rfloor} \sqrt{2}^{2j}
\sqrt{2}^{\lfloor \log_2 n \rfloor -j}
\\ = 1 - 2^{\lfloor \log_2 n \rfloor+1}
+ \sum_{j=0}^{\lfloor \log_2 n \rfloor}
\sqrt{2}^{\lfloor \log_2 n \rfloor +j}
\\ = 1 - 2^{\lfloor \log_2 n \rfloor+1}
+ \frac{\sqrt{2}^{\lfloor \log_2 n \rfloor +1}-1}{\sqrt{2}-1}
\sqrt{2}^{\lfloor \log_2 n \rfloor}.$$
To do the asmptotics observe that  the dominant term in the upper bound
is in $\sqrt{2}^{2\lfloor \log_2 n \rfloor}$ and in the lower bound it
is also in $\sqrt{2}^{2\lfloor  \log_2 n \rfloor}$ and additionally in
$2^{\lfloor \log_2 n \rfloor}.$
Joining the these terms from the upper and the lower bound we obtain
the asymptotics
$$\sqrt{2}^{2\lfloor \log_2 n \rfloor}
\in \Theta\left(2^{\log_2 n}\right) 
= \Theta\left(n\right).$$
Observe that there is a lower order term
$$\sqrt{2}^{\lfloor \log_2 n \rfloor}
\in \Theta\left(2^{1/2 \log_2 n}\right) 
= \Theta\left(\sqrt{n}\right).$$
The above is in agreement with what the Master theorem would produce.

Remark.
This is how we would produce a better upper bound.
Start from
$$\sum_{j=0}^{\lfloor \log_2 n \rfloor} 
2^j \sqrt{2^{\lfloor \log_2 n \rfloor +1 - j} -1}
= \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
2^{\lfloor \log_2 n \rfloor -j} 
\sqrt{2^{j+1} -1}
\\ = 2^{\lfloor \log_2 n \rfloor} 
\sum_{j=0}^{\lfloor \log_2 n \rfloor} 
\sqrt{2}^{-2j} 
\sqrt{2^{j+1} -1} 
= 2^{\lfloor \log_2 n \rfloor} 
\sum_{j=0}^{\lfloor \log_2 n \rfloor} 
\sqrt{2}^{1-j} 
\sqrt{1-2^{-j-1}} 
.$$
The  remaining sum term  is readily  seen to  converge to  a constant,
which is about $4.210094.$

Here is another computation in the same spirit 
MSE link.
