Closed form solution for recurrence I need to find a closed form solution for the following recurrence:
$T(m) \leq T(\sqrt m) + 1$, $T(1)=1$
I honestly don't have even have an idea where to start. Help would be greatly appreciated!
 A: $$T(m^{2^{0}})-T(m^{2^{-1}})\leq 1$$
$$T(m^{2^{-1}})-T(m^{2^{-2}})\leq 1$$
$$.$$
$$.$$
$$.$$
$$T(m^{2^{-(n-1)}})-T(m^{2^{-n}})\leq 1$$
Add all inequalities (notice that the sum in the LHS is telescoping):
$$T(m)-T(m^{2^{-n}})\leq n$$
$$T(m)-n\leq T(m^{2^{-n}})$$
A: If you're willing to give up the initial $T(1)=1$ and only define $T$ on $(1, \infty)$ then
if we denote $\lg m =\log_2m$, a closed-form solution (with equality, even) is 
$$
T(m) = a + \lg\lg m
$$
where $a$ is an arbitrary real number. To see this, observe
$$
\begin{align}
T(\sqrt{m})+1&=(a+\lg\lg\sqrt{m})+1\\
 &= a+1+\lg\lg(m^{1/2})\\
 & =a + 1 +\lg\left(\frac{1}{2}\lg m\right)\\
 &= a + 1 + \lg\left(\frac{1}{2}\right)+\lg\lg m\\
 &= a + 1 - 1 +\lg\lg m\\
 &= a+\lg\lg m = T(m)
\end{align}
$$ 
To see that I didn't just pull this out of thin air, the usual way to deal with recurrences involving $\sqrt{m}$ is to write the definition with $m=2^{2^k}$, as Amr did, and expand like this:
$$
\begin{align}
T(2^{2^k}) &= T(2^{2^{k-1}})+1\\
 &= T(2^{2^{k-2}})+1+1\\
 &= T(2^{2^{k-3}})+3\\
 &= T(2^{2^{k-4}})+4\\
\end{align}
$$
and so on, until you come to $T(2^{2^k}) = T(2^{2^0})+k$ (which is also why the initial value of such recurrences is usually taken to be 2, rather than 1).
