How fast does this sequence grow?

Question

I have the following recursive definition of a sequence of numbers:

$$a_{n+1}=(a_n)^{(a_{n-1})}$$

And $a_0=a_1=2$.

The first few terms are:

$$a_2=4$$ $$a_3=16$$ $$a_4=65536$$ $$a_5=1.1579209 \times 10^{77}$$

Obviously it grows fast, probably faster than exponential growth, maybe even faster than double exponential growth.

But it is hard for me to determine if it has something silly like 'triple' exponential growth or tetration growth.

How fast does this sequence grow?

Answer 1

This sequence exhibits tetrational growth. In particular, $a_{2n} \geq 2 \uparrow\uparrow (n+2)$ for $n \geq 2$.

We can prove this by induction.

For $n=2$, this is true since $a_4=65536=2 \uparrow\uparrow 4$.

Suppose it is true for $n=k$. Then $$a_{2(k+1)}=a_{2k+2}=a_{2k+1}^{a_{2k}} > 2^{a_{2k}} \geq 2^{2 \uparrow\uparrow (k+2)}= 2 \uparrow\uparrow (k+3) $$

This completes the induction hypothesis.

---

On the other hand, it is not hard to see that $$a_{n+1} = a_n^{a_{n-1}} \leq a_n^{a_n} < \left(2^{a_n}\right)^{a_n} = 2^{a_n^2} < 2^{2^{a_n}}$$

Since $a_1=2 \uparrow\uparrow 1$, we have $a_k<2 \uparrow\uparrow (2k+1)$.

Note $a \uparrow\uparrow b$ denotes up-arrow notation, in particular tetration in this case.

Answer 2

Let's compute the first few terms: $$a_5=\left(2^{16}\right)^{2^4}=2^{16 \cdot 16}=2^{256}\\ a_6=\left(2^{256}\right)^{2^{16}}=2^{2^8\cdot 2^{16}}=2^{2^{24}}\\ a_7=\left(2^{2^{24}}\right)^{2^{256}}=2^{2^{280}}\\ a_8=\left(2^{2^{280}}\right)^{2^{2^{24}}}=2^{2^{280}\cdot 2^{2^{24}}}=2^{2^{\left(280+2^{24}\right)}}$$ and the point is that $280$ is negligible compared to $2^{24}$. As the power towers get tall, we really don't care about the size of the bottom number. Here we have said the result is about the same whether it is $2$ or $2^{2^{280}}$ The neat thing is that under this approximation, the recurrence becomes $a_n=2^{a_{n-2}}$ once $n \gt 7$ and we can say $a_n$ is a stack of $\frac n2-1\ 2$'s topped by a $24$. The final $24$ is inconvenient to represent in up-arrow notation, but if we replace it with $2^{2^2}=16$ we have $a_n \gt 2\uparrow \uparrow (\frac n2+3)$ and I believe we can also show $a_n \lt 2\uparrow \uparrow (\frac n2+4)$, but my first approximation needs to be made precise to get it.