Question

Prove that $\mathbf{A}\mathbf{(}\mathbf{i}\mathbf{,}\mathbf{j}\mathbf{)}\mathbf{\ge }\mathbf{j}$whenever i and j 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.

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

We have to prove that A (i,j) > j whenever and are non-negative integers.

Since we know that A (m + 1, n) > A (m,n) whenever and are non-negative

integers,

It follows that

$\begin{array}{r}\mathrm{A}(\mathrm{i},\mathrm{j})\ge \mathrm{A}(\mathrm{i}-1,\mathrm{j})\\ \ge \mathrm{A}(\mathrm{i}-2,\mathrm{j})\\ \mathrm{So}\mathrm{we}\mathrm{get}\\ \mathrm{A}(\mathrm{i},\mathrm{j})\ge \mathrm{A}(\mathrm{i}-\mathrm{i},\mathrm{j})\\ =\mathrm{A}(0,\mathrm{j})\\ =2\cdot \mathrm{j}\\ \ge \mathrm{j}\end{array}$

Therefore,$A(i,j)\ge j$