Question

Prove that $\mathbf{A}\mathbf{(}\mathbf{m}\mathbf{+}\mathbf{1}\mathbf{,}\mathbf{n}\mathbf{)}\mathbf{\ge }\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

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,.....}.

Solution

Consider m and n be non-negative integers.

The definition of Ackermann’s function is as follows

$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\}$

Individuals shall prove that $A(m+1,n)\ge A(m,n)$using mathematical induction

This will be proved by double induction, first on m and n then

Step 3: Basis step

First consider m = 0

For all n, individuals have A (m,n) = 2n , where 2n > 2n

For n = 0 and n = 1 , individuals have A (m + 1, n) = 2n , where 2n > 2n

For n > 1 , individuals have

A (m + 1,n) = 2n , where 2n > 2n

Consider be a non-negative integer individuals assume that

A (m + 1,t) > A (m,t) ................(1)

Inductive step

Individuals prove that result holds for n + 1 , that is,

Greater than equal to,

A(m+2,n + 1) > A (m+1,n+1)

For n = 0 , individuals get 0 > 0

For n = 1, individuals get 2 > 2

Individuals assume that

A(m+2,n ) > A (m+1,n) .......(2)

Consider,

A(m+2,n + 1) = A (m+1,A (m + 2 , n))

Using definition,

$\begin{array}{r}\ge A(m+1,A(m+1,n\left)\right)\text{Use(1)}\\ \ge A(m+A(m+1,n\left)\right)\text{Use(2)}\\ =A(m+1,n+1)\\ \end{array}$

Using definition backward

Hence, it is proved by principle of mathematical induction.