Trouver un seuil tel qu'une fonction soit toujours plus grande que l'autre

Question

Étant donné la fonction définie récursivement $c$: $$ c (m, n) = begin {cas} 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 {et} n = 0 c (m-1, c (m, n-1)) & text {for} m > 1 text {et} n> 0 end {cas} $$

et la fonction $d$:

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

Les entrées millions de dollars et $n$ sont tous deux des nombres naturels.On me demande de trouver un $x$, tel que pour tous les nombres $y \ge x$, $c(y,y) > d(y)$.

J'ai réécrit les deux fonctions en Python afin de calculer certaines valeurs :

 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

Quelques entrées et sorties :

c(1, 1) = 3

c(2, 2) = 183

d(1) = 16

d(2) = 65536

d(3) = 20035299... 19156736, un nombre de 19729 chiffres.

Je crois que le seuil est $3$, comme c(3, 3) ne semble pas être calculable de manière réaliste étant donné qu'il y a plus de 19 000 chiffres dans UN(4, 2).Malheureusement, je n'ai aucune idée de comment le prouver.Toute aide serait très appréciée.

Answer 1

Comme vous vous en doutez, le seuil est bien de 3.

Voici une approche pour prouver que pour tous les nombres $y \ge 3$, $c(y,y) > d(y)$.

Étape 0, montrez que $c(\cdot, \cdot)$ est strictement croissant par rapport à chaque variable lorsque la deuxième variable n'est pas 0.
Étape 1, montrez que $c(1,n) \gt n^2$ pour tous $n\ge0$.
Étape 2, montrez que $c(2,n) \gt 2^n$ pour tous $n\ge0$.
Étape 3, montrez que $c(3,n)\gt d(n)$ pour tous $n\ge0$.
Étape 4, montrez que $c(y,y) \gt d(y) ext{ si }y\ge3$.

---

Exercice. Montre CA $c(3,y) > \underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{2y+2 ext{ copies de }2}$ pour tous $y\ge0$.