Find a threshold such that one function is always bigger than the other Given the recursively defined function  $c$:
$$c(m,n)=\begin{cases}0&amp;\text{for }m=0\\
n^2+n+1&amp;\text{for }m = 1\text{ and }n\ge 0\\
c(m-1, 1)&amp;\text{for }m&gt;1\text{ and }n=0\\
c(m-1,c(m,n-1))&amp;\text{for }m&gt;1\text{ and }n&gt;0\\
\end{cases}$$

and the function $d$:

$$d(n) = \underbrace{2^{2^{.^{.^{.^{.^{2}}}}}}}_{\text{$n+2$ }}$$

The inputs $m$ and $n$ are both natural numbers. I'm asked to find an $x$, such that for all numbers $y \ge x$, $c(y,y) &gt; d(y)$.

I rewrote the two functions using Python in order to calculate some values: 

 c(m, n):
    if m == 0:
        return 0
    else if m == 1 and n &gt;= 0:
        return n**2+n+1              # return n^2+n+1
    else if m &gt; 1 and n == 0:
        return c(m-1, 1)
    else if m &gt; 1 and n &gt; 0:
        return c(m-1, c(m, n-1))



 d(n):
    exp_num = n-1
    result = 2
    while exp_num != -1:
        result = 2**result           # result = 2^result
        exp_num = exp_num - 1
    final_result = 2**result         # final_result = 2^result
    return final_result



Some inputs and outputs: 

c(1, 1) = 3 

c(2, 2) = 183 

d(1) = 16 

d(2) = 65536 

d(3) = 20035299... 19156736, a number with 19729 digits.

I believe the threshold is $3$, as c(3, 3) doesn't seem to be realistically computable considering there are over 19K digit in A(4, 2). Unfortunately I have no idea how to prove this. Any help would be much appreciated.
As you suspected, the threshold is indeed 3.

Here is one approach to prove that for all numbers $y \ge 3$, $c(y,y) &gt; d(y)$.

Step 0, show that $c(\cdot, \cdot)$ is strictly increasing with respect to each variable when the second variable is not 0.
Step 1, show that $c(1,n) \gt n^2$ for all $n\ge0$.
Step 2, show that $c(2,n) \gt 2^n$ for all $n\ge0$.
Step 3, show that $c(3,n)\gt d(n)$ for all $n\ge0$.
Step 4, show that $c(y,y) \gt d(y)\text{ if }y\ge3$. 



Exercise. Show that $c(3,y) &gt; \underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{2y+2 \text{ copies of }2}$ for all $y\ge0$.