Comparing up-arrow's

Question

Is it true that $$3\uparrow^{n+1} 3\ >\ n\uparrow^n n $$

holds for every $n\ge 1$

Since $3\uparrow^{n+1}3=3\uparrow ^n 3\uparrow ^n 3$ and $3\uparrow^n3$ is much bigger than $n$ for $n\ge 3$, the power tower paradox seems to ensure this inequality, but I search for a rigorous proof.

Induction does not seem to help here.

Answer 1

You might be interested in the Knuth Arrow Theorem, proven by Sbiis Saibian. This states:

$$\forall a,b,d \geq 2, c \geq 3 : (a \uparrow^b c) \uparrow^b d < a \uparrow^b (c+d)$$

In the paper he also proves two lemma's:

• $a \uparrow^b c$ is strictly increasing with respect to any arguments. [L1]
• $f(b) = a \uparrow^b c \geq b+1$. [L2]

Both provided that $a>1$.

With this, we can see that $$3 \uparrow^n 3 = 3 \uparrow^{n-1} 3 \uparrow^{n-1} 3 \geq 3 \uparrow^{n-1} n > 3 \uparrow^{0} n = 3n > 2n$$

First step by definition, second step by L2, third step by L1, fourth step by definition.

Also we have $3 \uparrow^n n > n$, thus by L1 we have:

$$n \uparrow^n n < (3 \uparrow^n n) \uparrow^n n < 3 \uparrow^n 2n \leq 3 \uparrow^n 3 \uparrow^n 3 = 3 \uparrow^{n+1} 3$$

First step by L1, second by Knuth Arrow Theorem, third by the proven above, fourth by definition.