2
$\begingroup$

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.

  • 0
    Like @Steven said. In this case, $(\log n)^{\log_23}$ or $(\log_2 n)^{\log_23}$, see my answer.2011-11-14

3 Answers 3

2

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.

1

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.

  • 0
    $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.2011-11-14
0

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}$.

  • 0
    What you said was correct for $n$ of the form $2^{2^m}$, as Thomas Andrews said in his comment.2011-11-13