4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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?). $\endgroup$ – r.e.s. May 29 '16 at 17:35
  • $\begingroup$ @r.e.s. (1) fixed, thanks, (2) I mistyped the lemma. (I used $f(b)$) $\endgroup$ – wythagoras May 29 '16 at 19:03
  • $\begingroup$ 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.) $\endgroup$ – r.e.s. May 29 '16 at 19:28
  • $\begingroup$ (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$.) $\endgroup$ – r.e.s. May 29 '16 at 19:41

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.