Evaluate $\lim\limits_{n\rightarrow\infty} \mathrm{srt}_n\left({^{n+1}}2\right)$

210 Views Asked by At

Notation: ${^n}x = x^{x^{\cdots^x}}$ is tetration, i.e. $x$ to the power of itself $n$ times. $\mathrm{srt}_n(x)$ is the super $n$-th root, or the inverse function of ${^n}x$, which is well defined for $x\ge 1$. I can prove that $$ \lim\limits_{n\rightarrow\infty} \mathrm{srt}_n\left({^{n+1}}2\right) $$ converges to some value between about $\mathrm{srt}_3(256)\approx 2.2915$ and about $2.6$, but it is computationally intractable even for relatively small $n$. For example $^5 2\approx 2\times 10^{19728}$.

For ease of notation, we let $s_n = \mathrm{srt}_n(^{n+1}2)$. I would be very surprised if there's a nice closed form of $\lim\limits_{n\rightarrow\infty} s_n$, so I'm mostly interested here in how to approximate it other than a direct computation of the definition, which really isn't all that viable. As noted above, even computing $s_4$ is tough to do from the formula, though taking some logarithms can get you a bit further, it doesn't help much since tetration is much faster than exponentiation. Is there some trick that convert the formula to $s_n$ into something more tractable?

I can see how you could use the same approach as the one I used (see below) to get better lower bounds than $2.29$, but I suspect that would also become extremely difficult to use if you wanted any sort of precision (even one decimal place might be hard).


Proof of convergence: Clearly $s_n > 2$ for all $n$, so it suffices to show $s_n$ is decreasing. Observe:\begin{eqnarray} ^n s_n &=& 2^{\left(^n2\right)} = 2^{\left(^{n-1}s_{n-1}\right)}<(s_{n-1})^{\left(^{n-1}s_{n-1}\right)} = {^n}(s_{n-1}) \end{eqnarray} since $x\to {^n}x$ is increasing, this implies $s_n$ decreases.

Proof of lower bound: We prove that $s_n > c = \mathrm{srt}_3(256)$ for all $n$ by proving inductively ${^n} c \le\frac{\ln 2}{2\ln(c)} \left({^{n+1}}2\right)$. Since $\frac{\ln 2}{2\ln(c)} <1$, this means ${^n}c<{^{n+1}}2$. Taking $\mathrm{srt}_n$ of both sides shows $s_n>c$.

For the base case, we take $n=2$:\begin{eqnarray} c^{c^c} &=& 256 = 2^8\\ c^c \ln c &=& 8(\ln 2)\\ c^c \ln c &=& \frac12 (\ln 2) 16\\ c^c&=&\frac{\ln 2}{2\ln(c)} \left({^{3}}2\right) \end{eqnarray}

Now, for the inductive step. Suppose ${^n} c \le\frac{\ln 2}{2\ln(c)} \left({^{n+1}}2\right)$ for some $n\ge 2$. Observe that for $x > 4$ (this is not a tight bound):$$ \frac{\ln 2}{2\ln(c)} x < \frac1{\ln c}\ln\left(\frac{\ln 2}{2\ln(c)}\right) + \frac{\ln 2}{\ln c}x $$ Since ${^{n+1}2} > 4$, we therefore have \begin{eqnarray} {^n} c &\le&\frac{\ln 2}{2\ln(c)} \left({^{n+1}}2\right)\\ &<&\frac1{\ln c}\ln\left(\frac{\ln 2}{2\ln(c)}\right) + \frac{\ln 2}{\ln c}\left({^{n+1}2}\right) \end{eqnarray} Taking the $c$th power of both sides yields $$ {^{n+1}} c < \frac{\ln 2}{2\ln(c)} \left(^{n+2}2\right) $$ as desired. Hence we have inductively $$ {^{n}} c < \frac{\ln 2}{2\ln(c)} \left(^{n+1}2\right) $$ for all $n\ge 2$. Therefore $s_n > c$ for all $n$.


Computed with WolframAlpha, the first three terms of $s$ are \begin{eqnarray} s_1 &=& 4\\ s_2 &\approx& 2.74537...\\ s_3 &\approx& 2.58611...\\ s_4 &\approx& 2.57406... \end{eqnarray} Search query used for $s_2$, $s_3$, and $s_4$.

1

There are 1 best solutions below

4
On BEST ANSWER

First we discuss the convergence rate and then evaluate the result to 16 significant figures:


Convergence Rate:


Let us define $f_n(x)={}^nx\ln(x)=\ln({}^{n+1}x)$ and $g_n(x)=\ln(f_n(x))$.

$${}^{n+2}2={}^{n+1}(s_{n+1})$$

$${}^{n+1}2\ln(2)={}^n(s_{n+1})\ln(s_{n+1})$$

$$f_{n+1}(2)=f_n(s_{n+1})$$

We should be able to use $s_n$ as an estimate of $s_{n+1}$. Using a linear approximation we get:

$$f_n(s_{n+1})=f_n(s_n)(1+g_n'(s_n^\star)(s_{n+1}-s_n))$$

for some $s_n^\star\in(s_{n+1},s_n)$ via the mean value theorem. We also have $g_n'(s_n^\star)\ge g_n(s_n)$ for large $n$, which can be verified by log differentiating, which is very large. Substituting this in leaves us with

$$^{n+1}2\ln(2)={}^n(s_n)\ln(s_n)(1+g_n'(s_n^\star)(s_{n+1}-s_n))$$

Since we know that $^{n+1}2={}^n(s_n)$, this reduces to:

$$\ln(2)=\ln(s_n)(1+g_n'(s_n^\star)(s_{n+1}-s_n))$$

Solving for $s_{n+1}$ yields

$$s_{n+1}=s_n+\frac1{g_n'(s_n^\star)}\left(\frac{\ln(2)}{\ln(s_n)}-1\right)$$

Since $2<s_n$, we can see this is decreasing. Since $g_n'(s_n^\star)\to\infty$ tetrationally fast, we have $|s_{n+1}-s_n|\to0$ inversely tetrationally fast i.e. the digits accurate grows tetrationally. This means that we simply need to compute $s_n$ for sufficiently large $n$ and we should have all the digits we'll ever reasonably get.


Results


The general idea for comparing these giant power towers is to repeated apply logarithms and use logarithmic identities to make the problem tractable. From your links, we can already see that you attempted to apply the logarithm once, which yields:

$${}^3(s_4)\ln(s_4)=2^{2^{2^2}}\ln(2)$$

This is numerically evaluated by WolframAlpha to get:

$$s_4=2.574063140898349\dots$$

We can get $s_5$ by applying one more natural logarithm to get

$$^3(s_5)\ln(s_5)+\ln(\ln(s_5))=2^{2^{2^2}}\ln(2)+\ln(\ln(2))\tag{$\star$}$$

which can be numerically solved to give

$$s_5=2.574062876128519\dots$$

As it turns out, the computation of $s_6$ is also reasonably doable, by first applying the base 2 logarithm and then two natural logarithms:

\begin{align}^42\ln(2)+\ln(\ln(2))&=\ln(\ln(\log_2({}^72)))\\&=\ln(\ln(\log_2({}^6(s_6))))\\&=\ln({}^4(s_6)\ln(s_6)+\ln(\log_2(s_6)))\tag{$\star$}\end{align}

which is numerically solved, yielding:

$$s_6=2.574062876128519\dots$$

Side by side, this is:

\begin{align}s_4&=2.574063140898349\dots\\s_5&=2.574062876128519\dots\\s_6&=2.574062876128519\dots\tag{$\star\star$}\end{align}

That is, we can expect the answer to be accurate to the shown digits of $s_5$ and significantly many more digits accurate for $s_6$.

($\star$): One could alternatively just apply base 2 logarithms to get the equivalent expressions:

$$^42={}^3(s_5)\log_2(s_5)+\log_2(\log_2(s_5))$$ $$^42=\log_2({}^4(s_6)\log_2(s_6)+\log_2(\log_2(s_6)))$$

($\star\star$): Extrapolating with a secant approximation of $(\star)$ several times, we can get $s_5$ and $s_6$ to some more figures, assuming WolframAlpha is accurate, yielding:

$$s_5=2.5740628761285190463365497969711386694499537952\dots$$ $$s_6=2.5740628761285190463365497969711386694499537952\dots$$

though one must take care to note that WolframAlpha's precision may not be able to handle so many digits and a lot of cancellation occurs. If they are accurate though, then this will approximate the limit to the shown places.

From the shown convergence rates, we can be expect $s_4,s_5,$ and $s_6$ to be within roughly

$4:~{}^2(s_4)\log_{10}(s_4)\simeq4.7$

$5:~{}^3(s_5)\log_{10}(s_5)\simeq19727$

$6:~{}^4(s_6)\log_{10}(s_6)\simeq10^{19727}$

digits accurate of the limit respectively.