Q:

Recurrence equation $T(n)=3T(\sqrt{n}) +1$

I need to find an exact solution to the following recurrence using substitution (change of variables).
$$
T(n) =  3T(\sqrt{n}) + 1, \quad \text{ when } n > 2,
$$
and $$ T(2) = 1 .$$ I can't get it right. The best answer I came up with was $$
\frac 3 2  3^{\log_2 (\log_2 n)} - \frac 1 2,
$$ but when I try to prove it with induction, it doesn't seem to be the right answer.
Any help would be appreciated.

A:

The inhomogeneous form of the recurrence, with its constant term of $+1$, can be reduced to homogeneous form where the constant term is $0$, by subtracting a particular (e.g., constant) solution of the inhomogeneous equation.  Here the constant solution is $T(n) = -1/2$ so that $S(n) = T(n) + 1/2$ is the natural function to examine, and satisfies the simpler recurrence $S(n)= 3S(\sqrt{n})$.
For the equation to be well-defined, an interpretation of what $\sqrt{n}$ means should be fixed. For an integer recurrence you probably mean the greatest integer $\leq \sqrt{n}$.  For a positive real-valued recurrence one would stipulate the values of $T(n)$ on an interval containing $1$ and define the function on the rest of $(0,+\infty)$ using the recurrence.
The formula with $\log_2 \log_2 n$ does satisfy the recurrence for $n>1$, if $n$ is real-valued and the square roots are exact.  Unfortunately this form of $T(n)$ is undefined at $n=1$ and has a limit of $-1/2$ as $n \to 1$, which is inconsistent with the requirement that $T(1)=1$.  The trouble is that the unlimited ability to iterate the square root operation forces $T(n)$ toward $-1/2$ at $n=1$.  One has to ground the induction by clearly defining the "base case" of the recurrence and how it is reached in finitely many steps.  Then, instead of using logarithms, one can write a solution in terms of the quantity "number of iterations of $\sqrt{n}$ necessary to reduce $n$ to the initial value (or interval)". The logarithms are still important for expressing the approximate value of that quantity and thus the size of $T(n)$ for large $n$, but they are not an exact description of any solution with $T(1) \neq -1/2$.
EDIT: I am leaving the above as originally written, but the boundary condition is $T(2)=1$ and not $T(1)=1$ as I had thought. For that condition the algebraic formula in the question is correct at powers $2^{2^n}$ and definition at other values is best done in terms of the number of iterations to reduce $n$ to $2$ or less.

