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?

with $b_n = \ln a_n$ : $b_{n+1} = e^{b_n} b_{n-1}$, with $c_n = \ln b_n$ : $c_{n+1} = e^{c_n} + c_{n-1}$ — reuns, Mar 07 '16 at 19:39

wythagoras · Accepted Answer · 2016-03-07T18:56:49.220

3

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.

edited Mar 07 '16 at 18:56

answered Mar 07 '16 at 18:51

wythagoras

25,026

So at least tetrational growth? – Simply Beautiful Art Mar 07 '16 at 18:54
@SimpleArt I am currently updating the answer to also show that it is at most tetrational growth. – wythagoras Mar 07 '16 at 18:55

Ross Millikan · Answer 2 · 2016-03-07T19:19:30.327

1

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.

edited Mar 07 '16 at 19:19

answered Mar 07 '16 at 19:00

Ross Millikan

374,822

It would be better to replace the 24 with $2^{2^2}=16$. – wythagoras Mar 07 '16 at 19:13
@wythagoras: good point. I have incorporated that. – Ross Millikan Mar 07 '16 at 19:16
Actually, I just noticed an error in the answer, it should be $a_n \approx 2^{a_{n-2}}$, since the index of the exponent is two smaller. This gives actually that $a_{2n}$ is approximately a stack of $n-1$ 2s topped of with 24, and that $a_{2n+1}$ is approximately a stack of $n-1$ 2s topped of with 280. – wythagoras Mar 07 '16 at 19:17
@wythagoras: Yes. Fixed again. – Ross Millikan Mar 07 '16 at 19:24
On your last note: It is actually very hard to show such inequality, since induction is not possible. – wythagoras Mar 07 '16 at 19:35

How fast does this sequence grow?

2 Answers2