# If Graham's number used $4$s instead of $3$s, at which $G$ would that number be bigger than Graham's number?

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

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

## 1 Answer

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