Question

Prove that $\mathbf{A}\mathbf{(}\mathbf{m}\mathbf{,}\mathbf{n}\mathbf{+}\mathbf{1}\mathbf{)}\mathbf{>}\mathbf{A}\mathbf{(}\mathbf{m}\mathbf{,}\mathbf{n}\mathbf{)}$whenever m and n are nonnegative integers.

Short answer

It has been proved.

Step-by-step solution

Step 1:Introduction

A non negative integer is an integer that that is either positive or zero. It's the union of the natural numbers and the number zero. Sometimes it is referred to as , and it can be defined as the as the set {0,1,2,3,......} .

Step 2:Solution

Consider the Ackermann’s function

$A(m,n)=\left\{\begin{array}{l}2n\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}m=0\\ 0\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}m\ge 1\text{and}n=0\\ 2\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}m\ge 1\text{and}n=1\\ A(m-1,A(m,n-1\left)\right)\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}m\ge 1\text{and}n\ge 2\end{array}\right\}$

To show that $\mathrm{A}(\mathrm{m},\mathrm{n}+1)\ge \mathrm{A}(\mathrm{m},\mathrm{n})$, for all m and n are non-negative integers.

First prove that $A(m,k)>A(m,l)\text{, when}k>l$, when by using double induction.

Basis step:

The statement is true for m = 0 , because

$\begin{array}{r}k>ı\text{implies,}\\ A(0,k)=2k\\ >2ık>ı\\ =A(0,t)\end{array}$

Inductive step:

Assume that $A(m,x)>A(m,y)$for all non-negative integers andwith

Now show that that $A(m+1,k)>A(m+,1t)$

If k > t

Basis step

When i = 0 and k > 0, $A\left(m+1,t\right)=0$and

Either $A\left(m+1,t\right)=2$or $A\left(m+1,k\right)=A\left(m,A\left(m+1,k-1\right)\right)$

If m = 0 , 2A (1,K - 1) =$2^k$,

If m > 0 , this is greater than zero by inductive hypothesis.

role="math" localid="1668619182373" $\begin{array}{r}\mathrm{In}\mathrm{all}\mathrm{cases},=\mathrm{A}(\mathrm{m}+1,\mathrm{k})>0,\text{and in fact}\\ \mathrm{A}(\mathrm{m}+1,\mathrm{k})\ge 2\\ \mathrm{A}(\mathrm{m}+1,\mathrm{l})=2\\ \begin{array}{r}\mathrm{And}\mathrm{A}(\mathrm{m}+1,\mathrm{k})=\mathrm{A}(\mathrm{m},\mathrm{A}(\mathrm{m}+1,\mathrm{k}-1\left)\right)\text{with}\\ \mathrm{A}(\mathrm{m}+1,\mathrm{k}-1)\ge 2\end{array}\end{array}$

Hence the inductive hypothesis,

$\begin{array}{r}A(m,A(m+1,k-1\left)\right)\ge A(m,2)\\ >A(m,1)\\ =2\end{array}$

Inductive step

Assume that $A(m+1,r)>A(m+1,s)\text{, for all}r>s,s=0,1,\dots \dots l$

Then if k + 1 t + 1 it follows that

$\begin{array}{r}\mathrm{A}(\mathrm{m}+1,\mathrm{k}-1)=\mathrm{A}(\mathrm{m},\mathrm{A}(\mathrm{m}+1,\mathrm{k}\left)\right)\\ >\mathrm{A}(\mathrm{m},\mathrm{A}(\mathrm{m}+1,\mathrm{k}\left)\right)\\ =\mathrm{A}(\mathrm{m}+1,\mathrm{l}+1)\end{array}$

Therefore, $A(m,+1,k+1)>A(m,+1,l+1)\text{, for}k+1>l+1$

Hence from the principle of mathematical induction $A(m,n+1)>A(m,n)$, for all m and n are non-negative integers.