FANDOM


The basic definitions:

1. \(f_0(n)=n+1\)

2. \(f_{\alpha+1}(n)=f_\alpha^n(n)\)

FGH here is smaller than \(f_\omega(n)\), so the situation of when \(\alpha\) is a ordinal is ignored.


FGH and intuitional upper & lower bounds
lower FGH upper
1 \(2n\) \(2n\) \(2\uparrow n\)
2 \(2\uparrow n\) \(n2^n\) \(2\uparrow\uparrow n\)
3 \(2\uparrow\uparrow n\) \(...\) \(2\uparrow\uparrow\uparrow n\)

Lower bound

The most obvious lower bound of \(f_m(n)\) is \(2\uparrow^{m-1}n\), so let's prove it.  

1. Take \(f_2(n)\) as our starting point, for \(n\geq1\) , \(f_2(n)=n2^n\geq 2\uparrow n\) , the inequality holds.

2. Assume that \(f_m(n)\geq2\uparrow^{m-1}n\) for \(n\geq1\),

\(f_{m+1}(n)=\underbrace{f_m(f_m(...(f_m}_{n}(n))...))\)

\(2\uparrow^mn=\underbrace{2\uparrow^{m-1}2\uparrow^{m-1}2...\uparrow^{m-1}2}_{n}\)

lower bound FGH
1 \(2\) \(f_m(n)\)
2 \(2\uparrow^{m-1}2\) \(f_m(f_m(n))\)
3 \(2\uparrow^{m-1}2\uparrow^{m-1}2\) \(f_m(f_m(f_m(n)))\)
n \(2\uparrow^mn\) \(f_{m+1}(n)\)

Because that\(f_m(n)\geq2\) for \(n\geq1\) , and that every \(f_m(n)\geq2\uparrow^{m-1}n \) for \(n\geq1\), we know that \(f_{m+1}(n) \geq2\uparrow^{m-1}n\) for \(n\geq1\)

Thus, for every \(m,n \geq 1 , f_m(n)>2\uparrow^{m-1}n\)

Upper bound

The most intuitional upper bound of \(f_m(n)\) is probably \(2\uparrow^mn\), but actually its far faster than what speed that FGH grows at. And also, I failed to prove that :

So here is my first attempt :

1.\(2\uparrow n \geq f_1(n)\) for \(n\geq1\)

2.Assume that  \(2\uparrow^m n\geq f_m(n)\) for \(n\geq1\)

\(f_{m+1}(n)=\underbrace{f_m(f_m(...(f_m(}_{n}n))...))\)

\(2\uparrow^{m+1} n=\underbrace{2\uparrow^m2\uparrow^m...2\uparrow^m2}_{n}\)

FGH upper bound
1 \(f_m(n)\) \(2\)
2 \(f_m(f_m(n))\) \(2\uparrow^mn\)
3 \(f_m(f_m(f_m(n)))\) \(2\uparrow^m(2\uparrow^mn)\)
n \(f_{m+1}(n)\) \(2\uparrow^{m+1}n\)

You can see. Though we are sure about that \(2\uparrow^mn\) eventually outgrows \(f_m(n)\) , the upper bound was the underdog at the starting point, and we don't know when it will catch up the FGH. With this way we can't make the upper bound sure. 


Second attempt :

Since I didn't have the proper way to do it. I just made another guess. I was lucky enough to have found it. 

1. \(2\times(3\times n)>2\times(2\times n)>2n=f_1(n)\) for \(n\geq1\)

\(2\uparrow(3\times n)>2\uparrow(2\times n)>n2^n=f_2(n)\) for \(n\geq1\)

2.Assume that  \(2\uparrow^{m-1}(3n)>f_m(n)\)  for \(n,m\geq1\)

\(f_{m+1}(n)\)

\(=\underbrace{f_m(...(f_m(}_{n}n))...)\)

\(<\underbrace{2\uparrow^{m-1}(3\times(...(2\uparrow^{m-1}(3\times(}_{n}n))...))))\)

\(<\underbrace{2\uparrow^{m-1}(...(2\uparrow^{m-1}(}_{2n}n))...)\)  for \(n,m\geq0\)

3.

\(2\uparrow^m3n\)

\(=\underbrace{2\uparrow^{m-1}...2\uparrow^{m-1}2}_{3n}\)

\(=\underbrace{2\uparrow^{m-1}...2\uparrow^{m-1}}_{2n}(2\uparrow^mn)\)

\(\because 2\uparrow^mn \geq n\)  for \(m\geq0\)

\(\therefore 2\uparrow^m3n > f_{m+1}(n)\)  for \(n,m\geq0\)

Deedlit's proof

Though it's right in the comment of this post, I think it will look better if it's typed in mathematical formula.

Lemma 1 : \(2\uparrow^mn \geq 2n\) for \(m\geq0,n \geq 2\)

Proof of Lemma 1 :

When n = 2 ,  \(2\uparrow^m2=4\geq 2\times2\)

When m = 0 , \(2\uparrow^0n=2\times n=2n\)

Assume that \(2\uparrow^mn \geq 2n\)

\(2\uparrow^m(n+1)=2\uparrow^{m-1}(2\uparrow^mn)\geq2\uparrow^{m-1}2n\geq4n>2(n+1)\)

main proof :

\(m = 1: 2 \times 2n = 4n = 2 f_1(n)\)

\(n = 1: 2 \uparrow^{m-1} 2 = 4 = 2 f_m (1)\)

Main Induction step:

Assume that : \(2\uparrow^{m-1} (2n)\geq 2 f_m(n) \)

\(2\uparrow^{m} (2n)= (2\uparrow^{m-1})^n (2\uparrow^{m} n) \geq(2\uparrow^{m-1})^n (2n)\geq2(f_{m})^n (n) =2 f_{m+1}(n) \) for \(m,n\geq1\)

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.