Find a threshold such that one function is always bigger than the other

Question

Given the recursively defined function $c$: $$c(m,n)=\begin{cases}0&\text{for }m=0\\ n^2+n+1&\text{for }m = 1\text{ and }n\ge 0\\ c(m-1, 1)&\text{for }m>1\text{ and }n=0\\ c(m-1,c(m,n-1))&\text{for }m>1\text{ and }n>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) > 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 >= 0:
        return n**2+n+1              # return n^2+n+1
    else if m > 1 and n == 0:
        return c(m-1, 1)
    else if m > 1 and n > 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.

Answer 1

As you suspected, the threshold is indeed 3.

Here is one approach to prove that for all numbers $y \ge 3$, $c(y,y) > 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) > \underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{2y+2 \text{ copies of }2}$ for all $y\ge0$.