하나의 함수가 항상 다른 함수보다 큰 임계 값을 찾습니다.

Question

재귀 적으로 정의 된 함수 $ C $ : $$ c (m, n)=begin {사례} 0 & \ text {for} m= 0 \\ n ^ 2 + n + 1 & \ text {for} m= 1 \ text {및} 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 {사례} $$

및 함수 $ d $ :

$$ d (n)=undrebrace {2 ^ {2 ^ {^ {^ {^ {^ {^}}}}}} _ {\ text {$ n + 2 $}} $$

입력 $ M $ 및 $ n $ 은 모두 자연수입니다. 모든 숫자 $ y \ ge x $ 에 대해 $ x $ 을 찾아야합니다. , $ c (y, y)> d (y) $

나는 약간의 값을 계산하기 위해 파이썬을 사용하여 두 가지 기능을 다시 작성합니다.

 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

.

일부 입력 및 출력 :

c(1, 1) = 3

c(2, 2) = 183

d(1) = 16

d(2) = 65536

d(3) = 20035299... 19156736, 19729 숫자가있는 숫자.

임계 값은 $ 3 $ 입니다. a (4, 2). 불행히도 나는 이것을 증명하는 방법을 모르게하지 않습니다. 어떤 도움이 필요할 것입니다.

Answer 1

의심되는 것처럼 임계 값은 실제로 3입니다.

여기서 모든 숫자 $ y \ ge 3 $ , $ c (y, y) )> D (y) $

단계 0은 $ C (\ CDOT, \ CDOT) $ 이 0이 아닌 경우 각 변수와 관련하여 엄격하게 증가합니다.
$ C (1, n) \ gt n ^ 2 $ 모든 $ n \ ge0 $ < / span>.


2 단계에서 $ C (2, n) \ gt 2 ^ n $ 모든 $ n \ ge0 $ < / span>.


3 단계에서 $ C (3, N) \ GT D (n) $ 모든 $ N \ GE0 $ .

4 단계에서 $ C (y, y) \ gt d (y) \ text {if} y \ ge3 $ 을 보여줍니다.

---

운동. $ c (3, y)> \ undrebrace {2 ^ {2 ^ {\ cdot ^ {\ cdot ^ {\ cdot ^ 2}}}} _ _ {2Y + 2 \ text {} 2} $ \ span 클래스="수학 컨테이너"> $ y \ ge0 $ 에 대한 $} $ .