Question

Show that $\mathbf{A}\mathbf{(}\mathbf{1}\mathbf{,}\mathbf{n}\mathbf{)}\mathbf{=}{\mathbf{2}}^{\mathbf{n}}\mathbf{\text{whenever}}\mathbf{n}\mathbf{\ge }\mathbf{1}$.

Short answer

The statement is true.

Step-by-step solution

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.

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

Let P (n) be the statement that (1,n) =$2^n$,

Whenever$n\ge 1$

Basis step:

P (1) is true because

A (1,1) = 2

=$2^1$

Inductive step:

Assume that P (k) is true.

i.e. A(1,k) = $2^k$

We have to show that P (k + 1) is true.

Now

$\begin{array}{r}\mathrm{A}(1,\mathrm{k}+1)=\mathrm{A}(1-1,\mathrm{A}(1,\mathrm{k}+1-1\left)\right)\\ =\mathrm{A}(0,\mathrm{A}(1,\mathrm{k}\left)\right)\\ =\mathrm{A}\left(0,2^{\mathrm{k}}\right)\\ =2\cdot 2^{\mathrm{k}}\\ =2^{\mathrm{k}+1}\end{array}$

Therefore, A (1,k + 1) =$2^{k+1}$

Thus P (k + 1) is true.