Recurrence relation for the sequence $\sqrt{n}, \sqrt{\sqrt{n}}, \sqrt{\sqrt{\sqrt{\sqrt{n}}}}\cdots$

Question

To generate a sequence ($A$) like: $n^{\frac{1}{2}}, n^{\frac{1}{2^2}}, n^{\frac{1}{2^3}}, n^{\frac{1}{2^4}}, n^{\frac{1}{2^5}}, \cdots, n^{\frac{1}{2^k}}$ we can define a recursive function like:

$$ f(n) = \begin{cases} 1 & \text{if $n=2$}\\ f\left(\sqrt{n}\right) & \text{otherwise} \end{cases} $$

For simplicity, we can assume that every $2^i{th}$ root of $n$ is a perfect square of some integral power of $2$, so that any $n^{\frac{1}{2^i}}$ gives an integral power of $2$ and we are able to reach $n=2$ eventually (after $log_{_2}(log_{_2}(n))$ steps to be precise).

I was wondering what would be the similar recursive function for a sequence ($B$) like: $n^{\frac{1}{2}}, n^{\frac{1}{4}}, n^{\frac{1}{16}}, n^{\frac{1}{256}}, n^{\frac{1}{256^2}} \cdots$

$B\equiv n^{\frac{1}{2}}, n^{\frac{1}{4}}, n^{\frac{1}{16}}, n^{\frac{1}{256}}, n^{\frac{1}{256^2}}\cdots\equiv n^{\frac{1}{2^{2^0}}}, n^{\frac{1}{2^{2^1}}}, n^{\frac{1}{2^{2^2}}}, n^{\frac{1}{2^{2^3}}}, n^{\frac{1}{2^{2^4}}}\cdots\ $ converges in $log_{_2}(log_{_2}(log_{_2}(n))$ steps.

To visualize, the sequences are:

$A \equiv \sqrt{n}\to\sqrt{\sqrt{n}}\to\sqrt{\sqrt{\sqrt{n}}}\to\sqrt{\sqrt{\sqrt{\sqrt{n}}}}\to\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{n}}}}}\to\cdots$

and

$B \equiv \sqrt{n}\to\sqrt{\sqrt{n}}\to\sqrt{\sqrt{\sqrt{\sqrt{n}}}}\to\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{\sqrt{n}}}}}}}}\to\cdots$

Answer 1

I'm not sure your recurrence for $A$ is correct. I think what you are looking for is $f(k) = \begin{cases} n & \text{if }k = 0 \\ \sqrt{f(k-1)} & \text{if }k > 0 \end{cases}$

Then $f(0) = n, f(1) = \sqrt{n}, f(2) = \sqrt{\sqrt{n}}$ etc. $f(k) = n^{\frac{1}{2^k}}$ as required.

For sequence B, the general term is $f(k) = n^{\frac{1}{2^{2^k}}}$. We could write a recurrence

$f(k+1) = n^{\frac{1}{2^{2^{k+1}}}} = n^{\frac{1}{2^{\left(2^k+2^k\right)}}} = n^{\frac{1}{\left(2^{2^k}\right)\cdot \left(2^{2^k}\right)}} = \left(n^{\frac{1}{2^{2^k}}}\right)^\left(\frac{1}{2^{2^k}}\right) = f(k)^\left(\frac{1}{2^{2^k}}\right)$.

We can set the base case to be $f(0) = \sqrt{n} = n^{\frac{1}{2^{2^0}}}$

Answer 2

I've realised that there is no way we can achieve the recurrence (in terms of the input size $n$ alone) with just a single variable $n$, as we did in case of the sequence $A$ [with $f(n)=f(\sqrt{n})$].

For sequence $B$, we somehow need to keep tack of the iteration number $i$, like this:

$$ f(n)=f_1(n,\ 1) $$ $$ f_1\left(n,\ i\right) = \begin{cases} f_1\left(\sqrt{n},\ 2\right) & \text{if, $i=1$}\\ 1 & \text{if, $n=2$}\\ f_1\left(\sqrt[i]{n},\ i^2\right) & \text{otherwise} \end{cases} $$

Any other thought/suggestion is appreciated.