Which is the minimal number k, so that
$f_{\omega+1}(n) > G_n$ is true for all $n\ge k$ ?
For the definition of $f_{\omega+1}$ see Wikipedia: fast growing hierarchy
$G_n$ is defined by
$$G_0 = 4$$
$$G_{n+1} = 3 \uparrow^{G(n)} 3$$ for all $n\ge 0$. $\uparrow$ stands for knuth's up-arrow notation
I found the following upper bounds :
$$f_{\omega+1}(n) > [n,n,1,2] > n \rightarrow n \rightarrow (n-1) \rightarrow 2 >> G(n-2)$$ for $n\ge 3$
[n,n,1,2] means Bowers Arrow notation and $\rightarrow$ stands for conways arrow chain notation.
At n = 64, G(n) is catched up. So $k \le 64$
The inequality is true if and only if $n \ge 5$.
We will use the fact that
$$2 \uparrow^{m-1} (n+1) < f_m(n) < 2 \uparrow^{m-1} (2n)$$
for $m \ge 3, n \ge 2$. This of course implies that for $n \ge 3$,
$$2 \uparrow^{n-1} (n+1) < f_{\omega}(n) < 2\uparrow^{n-1}(2n)$$
Let $g(n) = 3\uparrow^n 3$. Then if $x > y, x\ge 3$,
$$f_\omega(x) > 2\uparrow^{x-1}(x+1) > 3\uparrow^{x-1}(x-1) \ge 3\uparrow^y y = g(y)$$
By induction we have $f_\omega^k(x) > g^k(y)$ for all $k$. So for $n > 4$,
$$f_{\omega+1}(n) = f_\omega^n(n) > g^n(4) = G(n)$$
On the other hand, if $x \le y, x \ge 3$,
$$f_\omega(x) < 2\uparrow^{x-1}(2x) < 2\uparrow^{x-1}(2\uparrow^{x-1}4) = 2\uparrow^x 4 < 3\uparrow^x 3 \le 3\uparrow^y 3 = g(y)$$
So
$$f_{\omega+1}(3) = f_\omega^3(3) < g^3(4) = G(3)$$
The cases $n=0,1,2$ can be directly computed:
$$f_{\omega+1}(0) = 0 < G(0) = 4$$ $$f_{\omega+1}(1) = 2 < G(1)$$ $$f_{\omega+1}(2) = f_\omega(f_\omega(2)) = f_\omega(8) = f_8(8) < G(2)$$
Okay, you probably want a proof of $2 \uparrow^{m-1} (n+1) < f_m(n) < 2 \uparrow^{m-1} (2n)$.
The left inequality is straightforward by induction:
$f_2(n) = n * 2^n \ge 2^{n+1}$, for $n \ge 2$.
$f_{k+1}(n) = f_k(f_k(\ldots(f_k(n))\ldots)) > 2\uparrow^{k-1}(2\uparrow^{k-1}(\ldots(2\uparrow^{k-1}(n+1))\ldots)) > 2\uparrow^k (n+1)$ for $n \ge 2$.
The right inequality is much more problematic, because of the "little bit extra" that $f_k$ has over Knuth arrow notation. We will require some lemmas.
Lemma 1. $a^b + c < a^{b+\frac{c}{a^b \log a}}$.
Proof: $a^b + c = a^b(1+\frac{c}{a^b}) = a^{b + \log_a (1+\frac{c}{a^b})} = a^{b + \frac{\log(1+\frac{c}{a^b})}{\log (a)}} < a^{b+\frac{c}{a^b \log a}}$.
Corollary 1. If $a^b \log a > 1, a^b+c < a^{b+c}$.
Let $E(n,a,b) = a^{a^{\cdots^{b}}}$, with n a's and one b.
Corollary 2. If $a^b \log a > 1, E(n,a,b)+c < E(n,a,b+c)$.
Proof: By induction on n.
Corollary 3. If $a^b \log a > 1, E(n,a,b)+c < E(n,a,b + \frac{c}{E(n,a,b)})$.
Proof: $E(n,a,b)+c = a^{E(n-1,a,b)}+c < a^{E(n-1,a,b + \frac{c}{E(n,a,b)})}$ (by Lemma 1) $ < a^{E(n-1,a,b+\frac{c}{E(n,a,b)})}$ (by Corollary 2) $ = E(n,a,b+\frac{c}{E(n,a,b)})$.
Lemma 2. $f_2^m(n) < E(m,2,2n+m-1)$.
Proof: By induction. $f_2(n) = n*2^n < 2^{2n} = E(1,2,2n)$.
$f_2^{m+1}(n) = f_2(f_2^m(n)) < f_2(E(m,2,2n+m-1)) < 2^{2E(m,2,2n+m-1)} = 2^{2^{E(m-1,2,2n+m-1)+1}}$
$ < 2^{2^{E(m-1,2,2n+m)}}$ (by Corollary 2) $= E(m+1,2,2n+m)$.
So $f_3(n) = f_2^n(n) < E(n,2,3n-1) < E(n,2,E(n,2,1)) = 2\uparrow\uparrow(2n)$.
Finally the general case. Let $E(m,n,a,b) = a \uparrow^n (a\uparrow^n(\ldots(a\uparrow^n b)\ldots))$. Assume $f_m(n) < 2\uparrow^{m-1}(2n)$.
Lemma 3. $f_m^k(n) < E(k,m-1,2,2n+k-1)$.
Proof: By induction. $f_m(n) < 2\uparrow^{m-1}(2n) = E(1,m-1,2,2n)$.
$f_m^{k+1}(n) = f_m(f_m^k(n)) < f_m(E(k,m-1,2,2n+k-1)) < E(1,m-1, 2, 2E(k,m-1,2,2n+k-1)) < E(1,m-1,2,E(k,m-1,2,2n+k)) = E(k+1,m-1,2,2n+k)$.
So $$f_{m+1}(n) = f_m^n(n) = E(n,m-1,2,3n-1) < E(n,m-1,2,E(n,m-1,2,1)) = E(2n,m-1,2,1) = 2 \uparrow^m (2n)$$
and we are done.