If $3\uparrow \uparrow\uparrow\uparrow3=G_1$, $ \quad G_2=\underbrace{3 \uparrow \ldots\uparrow3}_{G_1 \ \text{times}}, \quad G_3=\underbrace{3 \uparrow \ldots\uparrow3}_{G_2 \ \text{times}}$ , $ \quad\ldots \ , \quad G_n=\underbrace{3 \uparrow \ldots\uparrow3}_{G_{n-1} \ \text{times}}$ etc. until $G_{64}$

(where $n \in \mathbb{N}$ and $\quad \uparrow \quad$ is Knuth's up-arrow notation).

At which G would this number be bigger, if it had started with $4\uparrow \uparrow \uparrow \uparrow 4$ as $G_1$?.

  • 5
    $\begingroup$ Yes. ${}{}{}{}{}{}{}{}$ $\endgroup$ – Pedro Tamaroff Sep 15 '14 at 11:16
  • $\begingroup$ @PedroTamaroff: Are you a logician by any chance? $\endgroup$ – Alessandro Codenotti Sep 15 '14 at 11:33
  • 4
    $\begingroup$ @Pedro: Spooky! You answered Alessandro's question before he asked it. $\endgroup$ – TonyK Sep 15 '14 at 12:13
  • $\begingroup$ Bigger than what? $\endgroup$ – Alex M. Jan 3 '16 at 22:04
  • 2
    $\begingroup$ $G_{63}$ would still be smaller than Graham's number. $\endgroup$ – Peter Jan 12 '16 at 20:25

Let the Graham's number sequence be $G_1=3\uparrow^43$ and $G_{k+1}=3\uparrow^{G_k}3$ for $k\ge 1$. Now define the new sequence $A_1=4\uparrow^44$ and $A_{k+1}=4\uparrow^{A_k}4$ for $k\ge 1$. Then $A_k<G_{k+1}<A_{k+1}$ for all $k\ge 1$. In particular, $A_{63}<G_{64}<A_{64}$.

Proof (by induction): We show that $G_{k+1}>A_k+1$ for all $k\ge 1$.

  1. Base case: $G_2>A_1+1$ $$\begin{align}G_2 &= 3\uparrow^{G_1}3=3\uparrow^{G_1-1}(3\uparrow^{G_1-1}3)\\ &>(3\uparrow^{G_1-1}2)\uparrow^{G_1-1}(3\uparrow^{G_1-1}3-2)\\ &>4\uparrow^{4}4+1=A_1+1 \end{align}$$ where the first inequality follows from Saibian's theorem$^\dagger$, and the second inequality follows from $G_1=3\uparrow^43$.

  2. Induction: $G_{k}>A_{k-1}+1\implies G_{k+1}>A_{k}+1$ $$\begin{align}G_{k+1} &= 3\uparrow^{G_k}3=3\uparrow^{G_k-1}(3\uparrow^{G_k-1}3)\\ &>(3\uparrow^{G_k-1}2)\uparrow^{G_k-1}(3\uparrow^{G_k-1}3-2)\\ &>4\uparrow^{A_{k-1}}4+1=A_k+1 \end{align}$$ where again the first inequality follows from Saibian's theorem, and the second inequality follows from the induction hypothesis.

$\dagger$ Saibian's theorem: For any integers $b\ge 2,\,k\ge 2,\,m\ge 1,\,n\ge 1,$ $$(b\uparrow^k m)\uparrow^k n \ < \ b\uparrow^k (m+n).$$


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.