McCarthy 91 function

hbghlyj

定义$$M(n)=\begin{cases}n-10,&{\mbox{if }}n>100{\mbox{ }}\\M(M(n+11)),&{\mbox{if }}n\leq 100{\mbox{ }}\end{cases}$$证明: 对任何整数$ n ≤ 100$有$M(n) = 91$.

提示

Example A)
$$\eqalign{M(99)&= M(M(110))&\text{since }99 ≤ 100\\
      &= M(100)    &\text{since }110 > 100\\
      &= M(M(111)) &\text{since }100 ≤ 100\\
      &= M(101)   & \text{since }111 > 100\\
      &= 91       & \text{since }101 > 100}$$
Example B)\begin{align*}M(87)&= M(M(98))\\
     &= M(M(M(109)))\\
     &= M(M(99))\\
     &= M(M(M(110)))\\
     &= M(M(100))\\
     &= M(M(M(111)))\\
     &= M(M(101))\\
     &= M(91)\\
     &= M(M(102))\\
     &= M(92)\\
     &= M(M(103))\\
     &= M(93)\\
&\ldots&\text{ Pattern continues increasing till M(99), M(100) and M(101),}\\&&\text{ exactly as we saw on the example A)}\\
     &= M(101)  &  \text{since 111 > 100}\\
     &= 91      &  \text{since 101 > 100}\end{align*}