How can I show, that in the fast growing hierarchy, every sequence grows faster than the one before ?
A function $f(n)$ is said to grow faster than a function $g(n)$, if for every $k$ there exists $n_0$, such that $f(n)>g(n+k)$ for all $n\ge n_0$.
It is plausible that $g(n)=f^n(n)$ grows faster than $f(n)$, but how can I prove this and how can I handle the diagonalizations ?
Additional question : Is there an easier formulation of the above condition, for example by using landau symbols ?
I’m assuming that $f_0(m)=m+1$ and $f_{n+1}(m)=f_n^m(m)$ for $m,n\in\omega$. I will take it as known that each $f_n$ is an increasing function.
First show that $f_n(m)>m$ for $m>0$, so that $\langle f_n^k(m):k\in\omega\rangle$ is strictly increasing for $m>0$. Then show that $f_n(m)\ge 2m$ for $n\ge 1$. Both of these are inductions on $n$. It follows that
$$f_{n+1}(m)=f_n^m(m)=f_n^{m-1}\big(f_n(m)\big)\ge f_n^{m-1}(2m)=f_n^{m-2}\big(f_n(2m)\big)\ge f_n(2m)$$
for $n\ge 1$ and $m\ge 2$. An immediate consequence is that $f_{n+1}$ grows faster than $f_n$ for all $n\ge 1$, and it’s easy to check that $f_1(n)=2n$ grows faster than $f_0$.