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


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?

  • 2
    $\begingroup$ Relevant. $\endgroup$ – Zubin Mukerjee Mar 7 '16 at 18:30
  • $\begingroup$ 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}$ $\endgroup$ – reuns Mar 7 '16 at 19:39

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.

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

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.

  • $\begingroup$ It would be better to replace the 24 with $2^{2^2}=16$. $\endgroup$ – wythagoras Mar 7 '16 at 19:13
  • $\begingroup$ @wythagoras: good point. I have incorporated that. $\endgroup$ – Ross Millikan Mar 7 '16 at 19:16
  • $\begingroup$ 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. $\endgroup$ – wythagoras Mar 7 '16 at 19:17
  • $\begingroup$ @wythagoras: Yes. Fixed again. $\endgroup$ – Ross Millikan Mar 7 '16 at 19:24
  • $\begingroup$ On your last note: It is actually very hard to show such inequality, since induction is not possible. $\endgroup$ – wythagoras Mar 7 '16 at 19:35

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.