# How can I prove this sharp upper bound?

Here :

What are sharp lower and upper bounds of the fast growing hierarachy?

Deedlit mentions that for natural $m,n\ge 2$ and natural $k>n+log_2(n)$ , we have $$2\uparrow^{m-1}n<f_m(n)<2\uparrow^{m-1} k$$

The left inequality can be proven by induction. But what about the right inequality ? How can I bound $2\uparrow^{m-1} k$ in a way that induction can be applied ? Or do I need another idea ?

• Interesting. Never seen the RH inequality before either... Very interesting though! – Brevan Ellefsen Jun 1 '16 at 15:54
• Although hyperoperations satisfy a similar recursion, for the FGH it is not correct that $s(m,n+1)=f_m(n+1)=f_{m-1}(f_m(n))=s(m-1,s(m,n))$, because $f_m(n+1)=f_{m-1}^{n+1}(n+1) = f_{m-1}( f_{m-1}^{n}(n+1)) \neq f_{m-1}(f_m(n))$. – r.e.s. Jun 1 '16 at 23:04
• @r.e.s. You are right, I will have to delete my idea ... – Peter Jun 2 '16 at 10:25
• On second thought ... In the recursion theory literature there's another version of the FGH (not mentioned on the WP page) that's actually defined to satisfy a similar recursion. For finite indices, it's defined by $F_0(n):=n+1,\ F_{m+1}(0):=F_m(1),\ F_{m+1}(n+1):=F_{m}(F_{m+1}(n))$, which is the same as $F_0(n):=n+1,\ F_{m+1}(n):=F_{m}^{n+1}(1)$. This version is described on p.2 of [this article]. – r.e.s. Jun 6 '16 at 4:40
• @r.e.s. This version could be easier compared with up-arrows or Conway-chains, but I think it is not the one usually used. – Peter Jun 6 '16 at 8:44

So we will prove that for $m \ge 2, n \ge 3$, $f_m(n) \le 2\uparrow^{m-1}\lceil n + \log_2(n) + 1\rceil$.

Base case $m=2$: $f_2(n) = n 2^n = 2^{n+\log_2(n)} \le 2 \uparrow \lceil n + \log_2(n) + 1\rceil$.

Inductive step:

We assume that $f_m(n) \le 2\uparrow^{m-1}\lceil n + \log_2(n) + 1 \rceil \le 2 \uparrow^{m-1}(2n)$.

Lemma. For $m,n \ge 1$, $2\uparrow^m (n+2) > 2(2\uparrow^m n) + 2$.

Proof of Lemma: $2\uparrow^m(n+2) = 2 \uparrow^{m-1} (2 \uparrow^{m-1} (2\uparrow^m n)) \ge 2 \uparrow^0 (2\uparrow^0 (2\uparrow^m n)) = 4(2\uparrow^m n) > 2(2\uparrow^m n) + 2$ QED

Let $g(n) = 2 \uparrow^{m-1} n$ and $h(n) = 2 \cdot 2\uparrow^{m-1}(n)$. Then the Lemma is equivalent to $g(n+2) > h(n)+2$.

Lemma 2. $f_m^i(n) < h^i(2n)) < g^i(2n+2)$.

Proof: $$g^i(2n+2) = g^{i-1}(g(2n+2)) > g^{i-1}(h(2n)+2) > g^{i-2}(h^2(2n)+2) > g^{i-3}(h^3(2n)+2) > \ldots > h^i(2n) > f_m^i(n)$$

QED

Lemma 3. $2n+2 < 2 \uparrow^m \lceil \log_2(n) + 1\rceil$ for $m \ge 2, n \ge 3$.

Proof of Lemma 3: It suffices to prove the case $n = 2^k$, which reduces the lemma to

$$2 \cdot 2^k + 2 < 2 \uparrow^m ( k + 1)$$

Base case $k=2$: $2 \cdot 2^2 + 2 = 10 < 2\uparrow\uparrow 3 \le 2\uparrow^m 3$.

Inductive step:

$$2\uparrow^m(k+2) = 2\uparrow^{m-1}(2\uparrow^m(k+1)) \ge 2(2\uparrow^m(k+1)) > 2(2^{k+1}+2) = 2^{k+2} + 4 > 2^{k+2} + 2$$

QED

So, $$f_{m+1}(n) = f_m^n(n) < g^n(2n+2) <g^n(2\uparrow^m \lceil \log_2(n)+1\rceil) = 2\uparrow^m \lceil n+ \log_2(n) + 1 \rceil$$