4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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).$$

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – Peter Apr 21 '14 at 9:19
  • $\begingroup$ 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$ $\endgroup$ – Peter Apr 21 '14 at 9:26
  • $\begingroup$ 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 ? $\endgroup$ – Peter Apr 21 '14 at 9:28
  • 1
    $\begingroup$ @Peter - At the link, the operator sequence is defined as $([1],[2],[3],...) = (*,\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) = 3[5]3$, which is the same as your $G(1) = 3\uparrow^{4}3$, etc.) There is no inconsistency. $\endgroup$ – r.e.s. Apr 21 '14 at 12:12
  • $\begingroup$ @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. $\endgroup$ – Peter Apr 21 '14 at 14:45
4
$\begingroup$

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$$

$\endgroup$

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.