# For which n does the inequality $2 \uparrow^{n+1}n > 3\uparrow^n 3 +2$ hold?

For which n does the following inequality hold ?

$$2 \uparrow^{n+1}n > 3\uparrow^n 3 + 2$$

where $\uparrow$ stands for knuth's up-arrow notation.

I need this inequality to prove that

$$f_{\omega+1}(n) > G(n)$$

for $n\ge 8$

where $f_{\omega+1}(n)$ is a function from the fast growing hierarchy and G(n) is Graham's sequence

$$G(1) = 3\uparrow^4 3$$

$$G(n+1) = 3\uparrow^{G(n)} 3$$

for all n > 0.

## 2 Answers

The following "change-of-base" inequality is proved [here]: $$b\uparrow^{k}n < 2\uparrow^{k}((b-1)n) \quad(b \ge 3, k \ge 0, n \ge 1).$$ This gives $$3\uparrow^{k}3 \lt 2\uparrow^{k}6 \quad(k \ge 0).$$ Now $$2\uparrow^{k}6 \le 2\uparrow^{k}k \lt 2\uparrow^{k+1}k - 2 \quad(k \ge 6)$$ so $$3\uparrow^{k}3 \lt 2\uparrow^{k+1}k - 2 \quad(k \ge 6).$$

• Nice answer, but the base case in the link is k=0 , so it should be S(0). But it is easy to check that S(1) also holds for $b\ge 3$ – Peter Apr 21 '14 at 9:19
• Later in the link, Graham's sequence is defined by $G_1=3\uparrow^5 3$ , $G_{n+1}=3\uparrow^{G_n+1} 3$ – Peter Apr 21 '14 at 9:26
• As I remember, it should be $G_1=3\uparrow^4 3$,$G_{n+1}=3\uparrow^{G(n)}3$ instead. Did I miss a shift somewhere ? – Peter Apr 21 '14 at 9:28
• @Peter - At the link, the operator sequence is defined as $(,,,...) = (*,\uparrow,\uparrow\uparrow,...)$, starting with multiplication; i.e., $[k]$ is the same as $\uparrow^{k-1}$ for $k=1,2,3,...$. (That's why the link later refers to $g(1) = 33$, which is the same as your $G(1) = 3\uparrow^{4}3$, etc.) There is no inconsistency. – r.e.s. Apr 21 '14 at 12:12
• @res since you are very familar with such expressions, perhaps you can give an algorithm to comapre expressions of the form $a\uparrow^b c$ and $d\uparrow^e f$ for arbitary numbers a,b,c,d,e,f > 1. I asked this question on math overflow without getting an answer so far. – Peter Apr 21 '14 at 14:45

The inequality holds precisely when $n \ge 4$.

When $n=3$, we have

$$2 \uparrow^4 3 = 2 \uparrow^3 4 = 2\uparrow^2 (2 \uparrow^2 4) = 2 \uparrow^2 65536 < 3\uparrow^3 3 + 2 = 3\uparrow^2(3\uparrow^2 3) +2 = 3\uparrow^2 7625597484987 + 2$$

Using the fact that $2 \uparrow^m (n+2) > 3\uparrow^m n + 2$,(proven here) we have for $n \ge 4$:

$$2 \uparrow^{n+1} n \ge 2\uparrow^{n+1} 4 = 2\uparrow^n(2\uparrow^n 4) > 2 \uparrow^n 5 > 3 \uparrow^n 3 + 2$$