# Comparing up-arrow's

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.

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.

• A couple of observations: (1) Your lemma L1 fails when $a=c=2$; however, Saibian proved that it holds for integers $a\ge 2, b\ge 1, c\ge 3$. (2) You write "second step by L2", but I can see it only by an (omitted) induction proof that uses L2 only in its last step (maybe I'm not seeing a more direct way?). – r.e.s. May 29 '16 at 17:35
• @r.e.s. (1) fixed, thanks, (2) I mistyped the lemma. (I used $f(b)$) – wythagoras May 29 '16 at 19:03
• In Saibian's paper, the only thing I see that resembles your lemma L2 (but differs from it) is the lemma concerning what Saibian calls the "everywhere abundance" of the function(s) $f(c) = a\uparrow^b c > c$, i.e., functions of the "exponent" ($c$) rather than of the "base" ($a$) or the "degree" ($b$). Have I missed something? (But as I mentioned, a simple induction proof does give the result you want.) – r.e.s. May 29 '16 at 19:28
• (Also, you edited the theorem instead of fixing your lemma L1. Saibian proved the theorem for $a\ge 2, b\ge 2, c\ge 1, d\ge 1$, and your lemma L1 is valid for $a\ge 2,b\ge 1,c\ge 3$.) – r.e.s. May 29 '16 at 19:41