1
$\begingroup$

Regarding tetration, I know properties like ${}^a({}^bn)= {}^{ab}n$ do not hold in general. When $a=b=2$, for instance, we have $$ {}^2({}^2n)={}^2\left(n^n \right)=\left(n^n \right)^{\left(n^n \right)}=\left(n^{n^n} \right)^n=({}^3n)^n. $$ I wonder, however, if there is a way of simplifying the following nested tetration into a closed expression, with $f(n)={}^2n$, $$ f^k(n)={}^{\overbrace{2\, \cdots\,2 }^{k\text{ times}}}n. $$ For example, the first five terms are \begin{align} f^0(n)&=n\\ f^1(n)&={}^2n=n^n\\ f^2(n)&={}^2({}^2n)=n^{n^nn}\\ f^3(n)&={}^2({}^2({}^2n))=n^{n^{n^nn}n^nn}\\ f^4(n)&={}^2({}^2({}^2({}^2n)))=n^{n^{n^{n^nn}n^nn}n^{n^nn}n^nn}. \end{align} I can't find a relatively simple way of simplifying higher order terms. Any ideas?

Extra question: Could the case $k=n$ be "simpler" to simplify, somehow?

$\endgroup$
6
  • $\begingroup$ I am not quite sure, but the Steinhauser notation should be an iteration of $n^n$ , exactly what you want. I doubt however that a nice closed form exists. $\endgroup$ – Peter Nov 2 '19 at 13:31
  • $\begingroup$ Do you have a reference for Steinhauser notation? $\endgroup$ – sam wolfe Nov 2 '19 at 14:53
  • 1
    $\begingroup$ Maybe this is a good start : sites.google.com/site/largenumbers/home/3-2/Mega $\endgroup$ – Peter Nov 2 '19 at 14:56
  • $\begingroup$ @Peter Could the case $k=n$ be simpler to simplify, somehow? (added as an extra question) $\endgroup$ – sam wolfe Nov 9 '19 at 14:02
  • 1
    $\begingroup$ Yes! That's it. $\endgroup$ – sam wolfe Nov 10 '19 at 14:47
1
$\begingroup$

No, this does not simplify. It is notable that the specific case of $k=n$ is given by the Steinhaus-Moser notation by definition, but it does not give any other nice forms.

For the general case though, we have the bounds:

$${}^{a+b-1}n\le{}^a({}^bn)\le{}^{a+b}n$$

as an extended version of Knuth's arrow theorem and in your specific case:

$${}^{k+1}n\le f^k(n)\le{}^{k+2}n$$

for sufficiently large $n$.

The lower bound is easy to deduce by noting that:

$$f^{k+1}(n)=f^k(n)^{f^k(n)}\ge n^{({}^{k+1}n)}={}^{k+2}n$$

while the upper bound is deduced by instead proving the even tighter bound:

$$f^k(n)\le\underbrace{n~\widehat~~n~\widehat~~\dots~\widehat~~n~\widehat~~n}_k~\widehat~~(n+k)\le{}^{k+2}n$$

which gives

\begin{align}f^{k+1}(n)&=f^k(n)^{f^k(n)}\\&\le\underbrace{n~\widehat~~n~\widehat~~\dots~\widehat~~n}_k~\widehat~~(n^{n+k}+n+k)\tag{*}\\&\le\underbrace{n~\widehat~~n~\widehat~~\dots~\widehat~~n}_k~\widehat~~(n^{n+k}+n^{n+k})\\&=\underbrace{n~\widehat~~n~\widehat~~\dots~\widehat~~n}_k~\widehat~~(n^{n+k}\cdot2)\\&=\underbrace{n~\widehat~~n~\widehat~~\dots~\widehat~~n}_k~\widehat~~(n^{n+k}\cdot n)\\&=\underbrace{n~\widehat~~n~\widehat~~\dots~\widehat~~n}_k~\widehat~~(n^{n+k+1})\\&=\underbrace{n~\widehat~~n~\widehat~~\dots~\widehat~~n~\widehat~~n}_{k+1}~\widehat~~(n+k+1)\end{align}

where $(*)$ comes from pushing all of the exponents upwards using

$$a^bc\le(a^b)^c=a^{bc}$$

$\endgroup$

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.