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.

  • 5
    $\begingroup$ This recurrence only defines $T(n)$ for $n=2^{2^k}$. Prove using induction on $k$. $\endgroup$ – Thomas Andrews Nov 13 '11 at 19:06
  • $\begingroup$ He didn't say $n$ ranges over integers... $\endgroup$ – GEdgar Nov 14 '11 at 0:58
  • $\begingroup$ Instructions say that I can assume that the value of n is suitable such that argument of T is an integer. What does that mean exactly? $\endgroup$ – user1044048 Nov 14 '11 at 1:58
  • 1
    $\begingroup$ It means that either you define T(n) inductively on sets of iterated squares A^(2^n), starting from non-square values of A, where these sets are disjoint for different A and there is no relationship between the values of T on different sets; or you interpret $\sqrt{n}$ to be the square root rounded downward to an integer. $\endgroup$ – zyx Nov 14 '11 at 6:19
  • $\begingroup$ Note that $3^{\log_2 t}$ can also be written as $t^{\log_2 3}$, and that for complexity a lot of people consider a function of the form $t^\alpha$ 'simpler' than the alternate form. $\endgroup$ – Steven Stadnicki Nov 14 '11 at 6:43

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.


One is looking for the behaviour of sequences $(T(n))_{n\geqslant2}$ defined for every integer $n\geqslant2$. For any given integer $a\geqslant2$, apply the recursive relation to $$ t(k)=3^{-k}\cdot T(a^{2^k}). $$ One gets $t(k)=t(k-1)+3^{-k}$ for every positive integer $k$ hence $t(k)=t(0)+3^{-1}+3^{-2}+\cdots+3^{-k}$ for every nonnegative integer $k$. Using the partial sum of the geometric series, this yields, for every nonnegative integer $k$, $$ \color{red}{T(a^{2^k})=3^k\cdot T(a)+2^{-1}\cdot(3^k-1)}. $$ For example, since one assumes that $T(2)=1$, $$ T(2^{2^k})=2^{-1}\cdot(3^{k+1}-1). $$ Note that the values $T(a)$ for every nonsquare integer $a\geqslant2$ are free since the relation one would get for $T(a)$ involves $T(\sqrt{a})$, which does not exist since $T(n)$ is only defined for (some) integer values of $n$.

It seems that the only way to get a single simple equivalent of $T(n)$ when $n\to\infty$ is to finely tune all these initial values of $T$ as follows. Assume there exists a constant $c$ such that for every nonsquare integer $a\geqslant2$, $$ T(a)=c\cdot\left(\log_2a\right)^{\log_23}-2^{-1}. $$ Then, for every positive integer $n\geqslant2$, $$ T(n)=c\cdot(\log_2n)^{\log_23}-2^{-1}. $$ Since the initial condition $T(2)=1$ imposes the value $c=\frac32$, one gets the convergence $\color{red}{R(n)\to\frac32}$ when $n\to\infty$, with $$ \color{red}{R(n)=\frac{T(n)}{(\log_2n)^{\log_23}}}. $$ For other initial conditions (that is, other values of $T(a)$ for $a\geqslant3$ non square), the sequence of ratios $(R(n))_{n\geqslant2}$ diverges in the sense that it oscillates without converging to a finite limit.

  • $\begingroup$ $T(1)$ is not determined by the recursion, which is given for $n > 2$ only, with $2$ being an initial value. What happens at or near $n=1$ (with $1$ as the value where a boundary condition is imposed) is a more delicate question as explained in the other answer. $\endgroup$ – zyx Nov 14 '11 at 6:45

Try the simpler $R(m)=3R(m-1)+1$ when $m>0$ and $R(0)=1$.

Then you should be able to show by induction this is $R(m)=\frac 3 2 3^m - \frac 1 2$.

Now let $m=\log_2 (\log_2 n)$ or $n=2^{2^m}$.

  • $\begingroup$ So this basically means that my answer is correct and exact answer for the given recurrence? I just tried to prove it with wrong value of n? $\endgroup$ – user1044048 Nov 13 '11 at 23:39
  • $\begingroup$ What you said was correct for $n$ of the form $2^{2^m}$, as Thomas Andrews said in his comment. $\endgroup$ – Henry Nov 13 '11 at 23:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.