Define the functions $$f_0(x,y)=\begin{cases}x! & \text{if } y=1\\f_0(x,y-1)! & \text{otherwise}\end{cases}$$ and $$ f_1(x,y,z)=\begin{cases} f_0(x,y) & \text{if } z=1\\ f_0(x,f_1(x,y,z-1)) & \text{otherwise} \end{cases} $$ Furthermore, define the function $$ g_1(x,y,z)=\begin{cases} x^y & \text{if } z=1\\ x^{g_1(x,y,z-1)} & \text{otherwise} \end{cases} $$ I would like to know the value of $\lim_{i\to \infty}\left(\frac{f_1(i,i,i)}{g_1(i,i,i)}\right)$ (whether it tends to infinity).
My attempt
We know $f_0(x,1) \le x^x =g_1(x,x,1)$. I guess that $f_0(x,y) \le g_1(x,x,y)$. They seem to be about the same order of magnitude. I couldn't find any other way to compare $f_1$ and $g_1$.
Your guess that $\lim_{i\to \infty}\frac{f_1(i,i,i)}{g_1(i,i,i)} \rightarrow \infty$ is absolutely correct
We start by proving $x!!!!!... (x\;times) > x^x$
For that, we go back one step and first prove $x! > x + 1 \;\forall x > 2$
Considering the product of the first 2 terms of x!, i.e. x(x-1).
$x! > x(x-1) \because x! = x(x-1)(x-2)...$ & all other factors like (x-2), (x-3), (x-4) > 1.
So now we can easily prove $x(x-1) > x + 1 \;\forall x > 2 \;(\because x^2 - x > x + 1 \;\forall x > 2 \;\because x^2 - 2x - 1 > 0 \;\forall x \in Z \;\cap > 2$
So let us prove $x!!!!!... (x\;times) > x^x$
$x! > x \;\forall x > 1 \because \frac{x!}{x} = (x-1)(x-2).. > 1 \because$ each term getting multiplied is > 1.
Multiplying x on both sides we get :
$x \cdot x! > x^2$
But $x!! > x \cdot x! \;\because \frac{x!!}{x!} = (x!-1)(x!-2)(x!-3).. \;\&\; x!-1 > x \;\&\; (x!-2), (x!-3) .. > 1$
$\therefore x!! > x \cdot x! > x^2$
We can extend this property $(x!!!..(n\;times) > x^n)$ to all natural numbers using induction or by using such a proof as stated above.
Let us now find $f_0(x,y)$
$f_0(x,1) = x!, f_0(x,2) = f_0(x,1)! = (x!)! = x!!, f_0(x,3) = f_0(x,2)! = (x!!)! = x!!!$ and so on
$\therefore f_0(x,y) = x!!!..(y\;times)$
Now let us find $f_1(x,y,z)$
$f_1(x,y,1) = f_0(x,y) = x!!!..(y\;times), f_1(x,y,2) = f_0(x,f_1(x,y,1)) = f_0(x,x!!!...(y\;times)) = x!!!..(x!!!..(y\;times)), f_1(x,y,3) = f_0(x,f_1(x,y,2)) = f_0(x, x!!!..(x!!!..(y\;times))) = x!!!..(x!!!..(x!!!..(y\;times)))$
$\therefore f_1(x,y,z) = x!!!..(x!!!...(x!!!..(...(x!!!..(y\;times))..))))$ where x appears z times.
Now let us find $g_1(x,y,z)$
$g_1(x,y,1) = x^y, g_1(x,y,2) = x^{g_1(x,y,1)} = x^{x^y}, g_1(x,y,3) = x^{g_1(x,y,2)} = x^{x^{x^y}}$
$\therefore g_1(x,y,z) = x^{x^{x^{.^{.^{.^{y}}}}}}$ where x appears z times.
Now let us prove that $\lim_{x\rightarrow\infty}\frac{x!!!...(x\;times)}{x^x} \rightarrow \infty$
We know $\lim_{x\rightarrow\infty}\frac{x!}{x} \rightarrow \infty \because \lim_{x\rightarrow\infty}\frac{x!}{x} = \lim_{x\rightarrow\infty}(x-1)(x-2).. \rightarrow \infty$
Multiply numerator and denominator by x and performing the same manipulation as before, we get $\frac{x!!}{x^2} > \frac{x!}{x}$
$\therefore \lim_{x\rightarrow\infty}\frac{x!!}{x^2} > \lim_{x\rightarrow\infty}\frac{x!}{x} \rightarrow \infty$
Again we can extend this property ($\lim_{x\rightarrow\infty}\frac{x!!!...(n\;times)}{x^n} \rightarrow \infty$) to all natural numbers using induction or by using such a proof as stated above
Now we know that $x!!!..(y\;times) > x^y$ and we observe that $f_1(x,y,z) = x!!!..(x!!!...(x!!!..(...(x!!!..(y\;times))..))))$ where x appears z times, $g_1(x,y,z) = x^{x^{x^{.^{.^{.^{y}}}}}}$ where x appears z times.
Taking $f_1(x,y,1)$ i.e. x!!!..(y times), we have proved that it is > $g_1(x,y,1)$ i.e. $x^y$
$\therefore$ $f_1(x,y,2) = x!!!.. (x!!..(y times)) > x!!..(x^y\;times) > x^{x^y}$ which is $g_1(x,y,2)$
Doing this for z = 3, 4, .. (z-1) yields the same result
$\therefore f_1(x,y,z-1) > g_1(x,y,z-1) \implies x!!..(f_1(x,y,z-1)\;times) > x!!..(g_1(x,y,z-1)\;times)$
But $x!!..(f_1(x,y,z-1)\;times) = f_1(x,y,z)$
$\therefore f_1(x,y,z) > x!!..(g_1(x,y,z-1)\;times)$
Now we can use the above proved property $\lim_{x\rightarrow\infty}\frac{x!!!...(n\;times)}{x^n} \rightarrow \infty$
Putting x = y = z = i and $g_1(i,i,i-1)$ = n, we get :
$\lim_{i\rightarrow\infty}\frac{x!!!...(g_1(i,i,i-1)\;times)}{x^{g_1(i,i,i-1)}} \rightarrow \infty$
But we know $x^{g_1(i,i,i-1)} = g_1(i,i,i) \;\&\; f_1(i,i,i) > i!!..(g_1(i,i,i-1)\;times)$ to get :
$\lim_{i\rightarrow\infty}\frac{f_1(i,i,i)}{g_1(i,i,i)} > \lim_{i\rightarrow\infty}\frac{x!!!...(g_1(i,i,i-1)\;times)}{x^{g_1(i,i,i-1)}} \rightarrow \infty$
I know the language I wrote the answer in may be confusing but unfortunately I could not find a better way to present my argument, if you have any difficulty in understanding my solution, you can comment and I'll be sure to answer your problems at the earliest.