# Nested Tetration properties

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?

• 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. – Peter Nov 2 '19 at 13:31
• Do you have a reference for Steinhauser notation? – sam wolfe Nov 2 '19 at 14:53
• Maybe this is a good start : sites.google.com/site/largenumbers/home/3-2/Mega – Peter Nov 2 '19 at 14:56
• @Peter Could the case $k=n$ be simpler to simplify, somehow? (added as an extra question) – sam wolfe Nov 9 '19 at 14:02
• Yes! That's it. – sam wolfe Nov 10 '19 at 14:47

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