Encontrar un umbral de tal manera que una función sea siempre más grande que la otra

Question

Dada la función recursivamente definida $ c $ : $$ C (m, n)=comienzan {casos} 0 & \ texto {para} m= 0 \\ n ^ 2 + n + 1 & \ texto {para} m= 1 \ texto {y} n \ ge 0 \\ C (M-1, 1) & \ texto {para} m> 1 \ texto {y} n= 0 \\ C (M-1, C (M, N-1)) & \ texto {para} m> 1 \ texto {y} n> 0 \\ \ End {casos} $$

y la función $ d $ :

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

Las entradas $ m $ y $ n $ son los números naturales. Me piden que encuentre un $ x $ , de modo que para todos los números $ y \ ge x $ , $ c (y, y)> d (y) $ .

Reescribí las dos funciones usando Python para calcular algunos valores:

 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

Algunas entradas y salidas:

c(1, 1) = 3

c(2, 2) = 183

d(1) = 16

d(2) = 65536

d(3) = 20035299... 19156736, un número con 19729 dígitos.

Creo que el umbral es de $ 3 $ , como c(3, 3) no parece ser realista computable teniendo en cuenta que son más de 19K dígitos en a (4, 2). Lamentablemente, no tengo idea de cómo probar esto. Cualquier ayuda sería muy apreciada.

Answer 1

Como lo presenta, el umbral es de hecho 3.

Aquí hay un enfoque para demostrar que para todos los números $ y \ ge 3 $ , $ c (y, y )> D (y) $ .

Paso 0, muestra que $ c (\ cdot, \ cdot) $ está aumentando estrictamente con respecto a cada variable cuando la segunda variable no es 0.
Paso 1, muestra que $ c (1, n) \ gt n ^ 2 $ para todos $ n \ ge0 $ < / span>.
Paso 2, muestre que $ c (2, n) \ gt 2 ^ n $ para todos $ n \ ge0 $ < / span>.
Paso 3, Muestre que $ c (3, n) \ gt d (n) $ para todos $ n \ ge0 $ .
Paso 4, muestre que $ c (y, y) \ gt d (y) \ texto {if} y \ ge3 $ .

---

Ejercicio. Mostrar que $ C (3, y)> \ Subbrace {2 ^ {2 ^ {\ CDOT ^ {\ CDOT ^ {\ CDOT ^ 2}}}}} _ {2y + 2 \ texto {copias de} 2} $ para todos $ y \ ge0 $ .