Question

Show that A (m,2) = 4 whenever m > 1 .

Short answer

The statement is true.

Step-by-step solution

 Step 1: Introduction

Mathematical Induction is a mathematical technique which is used to prove a statement, a formula or a theorem is true for every natural number. Step 1(Base step) − It proves that a statement is true for the initial value.

Step 2: Basis step

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

Let p (n) be the statement that A (m,2) = 4 whenever m > 1

Basis step:

p(1) is true because

$\begin{array}{r}A(1,2)=A(1-1,A(1,2-1\left)\right)\\ =A(0,A(1,1\left)\right)\\ =A(0,2)\\ =2.2\\ =4\end{array}$

Induction step:

Assume that p (k) is true.

i.e. A (k,2) = 4

We know to show that p (k + 1) is true.

Now,

$\begin{array}{r}\mathrm{A}(\mathrm{k}+1,2)=\mathrm{A}(\mathrm{k}+1-1,\mathrm{A}(\mathrm{k}+1,2-1\left)\right)\\ \mathrm{A}(\mathrm{k},\mathrm{A}(\mathrm{k}+1,1\left)\right)\\ =\mathrm{A}(\mathrm{k},2)\\ =4\text{(By inductive hypothesis})\end{array}$

Therefore A (k + 1,2) = 4

Thus, p (k + 1 ) is true.