Knuth's arrow up notation again

Question

Consider the following recursion : $$ a(1)=3! $$ $$ a(n+1) = a(n)! \quad\hbox{for all $n\geq 1$} $$ For a given $n$, how can the number $m$ with $$ 10 \uparrow \uparrow m < a(n) < 10 \uparrow \uparrow (m+1) $$ be calculated ?

With induction, I got $$ 10 \uparrow \uparrow m < a(m+1) $$

for all $m$.

Answer 1

I will use Stirling's approximation, which isn't exact, but one can show that it doesn't effect the result. First, I define $\text{slog}_{10}(z)$ as the inverse of Tetration, extended by Kneser's method to real numbers, and I take the slog of the Op's sequence of "a" numbers.

$\text{slog}_{10}(a(1)) = \text{slog}_{10}(3!) = \text{slog}_{10}(6) \approx 0.852230828 \\ \text{slog}_{10}(a(2)) = \text{slog}_{10}(6!) = \text{slog}_{10}(720) \approx 1.56653651 \\ \text{slog}_{10}(a(3)) = \text{slog}_{10}(720!) \approx \text{slog}_{10}(2.60121894 \times 10^{1746}) \approx 2.62213791 \\ \text{slog}_{10}(a(4)) = \text{slog}_{10}((720!)!) \approx 1 + \text{slog}_{10}(\log_{10}(2.60121894 \times 10^{1746}!))) \\ \text{slog}_{10}(a(4)) = \text{slog}_{10}((720!)!) = 1+\text{slog}_{10} (\log_{10}((720!)!)) \\ \quad\quad\> = 1+\text{slog}_{10} ((720!)(\ln(720!)-1)/\ln(10) + O(\ln(720!)) \\ \quad\quad\> \approx 1 + \text{slog}_{10}(4.54167855 \times 10^{1749}) \approx 3.62224425$

The second line of the last equation makes use of Stirling's approximation for the log of factorial, $\ln(z!) = z(\ln(z)-1)+O\ln(z)$. In this case the $O(\ln(z)) \approx 4000$ is negligible when added to a number with 1749 decimal digits, leading to an overall error term of $O(1/a(3))$.

$\text{slog}_{10}(a(5)) = \text{slog}_{10}(720!!!) = 1+\text{slog}_{10} (\log_{10}(720!!!)) \\ \quad\quad = 2+\text{slog}_{10} (\log_{10}(\log_{10}(720!!!)))$

For a(5), Stirling's approximation can be used for the log(log(720!!!)) as well,

$ \log_{10}(\log_{10}(z!)) = \log_{10}((z)(\ln(z)-1)/\ln(10) + O(\ln(z)) \\ \log_{10}(\log_{10}(z!)) = \log_{10}(z) + \log_{10}(\ln(z)-1) - \log_{10}(\ln(10)) + O(1/z) \\ \log_{10}(\log_{10}(720!!!)) = \log_{10}(720!!) + \log_{10}(\ln(720!!)-1) - \log_{10}(\ln(10)) + O(1/720!!)$

Here the Stirling's equation error term may seem large, 10^1750, until you realize it is being added to a number with 10^10^1750 digits. In the last eqution, the $+ \log_{10}(\ln(720!!)-1) - \log_{10}(\ln(10))\approx 1750$ term isn't significant either, because it is being added to a number with 1749 digits. So for (n>=5) we have the same equation as a(4) accurate to >1740 decimal digits, $\log_{10}(\log_{10}(720!!!)) \approx \log_{10}(720!!)+1750 \approx 4.54 \times 10^{1749}$. The slog of both numbers will also be the same, because the log of both numbers is the same, accurate to >1740 decimal digits. Finally, this results in the following approximation.

$\text{slog}_{10}(a(n)) \approx 1+ \text{slog}_{10}(a(n-1)) + O\frac{1}{a(n-2)}$

This in turn justifies the answer to the Op's question. $$ 10 \uparrow \uparrow (n-1) < a(n) < 10 \uparrow \uparrow (n)$$

Answer 2

With induction, I got

$10 \uparrow \uparrow m < a(m+1)$

for all m

Aren't you done then? If you got proof up to that point, your $n$ is given anyway, so continue assuming $m = n-1$

EDIT: Patrick Da Silva is right, I totally forgot about the other direction. Can you build a relation between $a(m+1)$ and $10 \uparrow \uparrow m+1$ by induction too? If you can show that $a(m+1) < 10 \uparrow \uparrow m+1$ is valid for $\forall m$ too then the above assumption should work.