# 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&\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.

• Look up the Ackermann function for more details – narek Bojikian Dec 28 '19 at 6:10

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$$.

• Thank you for answering, I could show that c is monotone increasing, but could you elaborate why 1, 2, 3 are necessary? – iMazing Dec 27 '19 at 10:42
• I also edited my Python implementation of d(n) – iMazing Dec 27 '19 at 10:59
• "Could you elaborate why 1, 2, 3 are necessary?" I am not sure of what you were asking. They are just part of my approach to prove 3 is the threshold. Each of them can be proved by simple induction using what have been proved in previous steps. – John L. Dec 27 '19 at 14:05
• I wasn't sure why we had prove the previous steps. Thank you, I will try to solve and get back to you later today. – iMazing Dec 27 '19 at 15:47
• I'm having some trouble proving 3. After using the induction hypothesis and the result from 2, I end up at 2^(2^c(3,n)) > d(n+1). Why does this hold? I know that c(3,n) > d(n) (induction hypothesis) but that's about it. – iMazing Dec 27 '19 at 17:24