Encontre um limite tal que uma função seja sempre maior que a outra

Question

Dada a função definida recursivamente $c$: $$ c (m, n) = begin {casos} 0 & text {for} m = 0 n^2+n+1 & text {for} m = 1 text {e} n ge 0 c (m-1, 1) & text {for} m> 1 text {e} n = 0 c (m-1, c (m, n-1)) & text {for} m > 1 text {e} n> 0 end {casos} $$

e a função $d$:

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

As entradas $m$ e $n$ são ambos números naturais.Me pedem para encontrar um $x$, tal que para todos os números $y \ge x$, $c(y,y) > d(y)$.

Reescrevi as duas funções usando Python para calcular alguns 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

Algumas entradas e saídas:

c(1, 1) = 3

c(2, 2) = 183

d(1) = 16

d(2) = 65536

d(3) = 20035299... 19156736, um número com 19.729 dígitos.

Acredito que o limite seja $3$, como c(3, 3) não parece ser realisticamente computável, considerando que existem mais de 19 mil dígitos em A(4, 2).Infelizmente não tenho ideia de como provar isso.Qualquer ajuda seria muito apreciada.

Answer 1

Como você suspeitava, o limite é de fato 3.

Aqui está uma abordagem para provar que para todos os números $y \ge 3$, $c(y,y) > d(y)$.

Passo 0, mostre que $c(\cdot, \cdot)$ é estritamente crescente em relação a cada variável quando a segunda variável não é 0.
Passo 1, mostre que $c(1,n)\gtn^2$ para todos $n\ge0$.
Passo 2, mostre que $c(2,n)\gt2^n$ para todos $n\ge0$.
Passo 3, mostre que $c(3,n)gtd(n)$ para todos $n\ge0$.
Passo 4, mostre que $c(y,y) \gt d(y) ext{ se }y\ge3$.

---

Exercício. Mostre isso $c(3,y) > \underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{2y+2 ext{ cópias de }2}$ para todos $y\ge0$.