Question

Define a function A: N x N -> N as follows: A(m, n) ={2n, if m= 0; 0, if m≥1 and n= 0; 2, if m≥1 and n= 1; A(m-1, A(m, n-1)), if m≥1 and n≥2

Show that A(m, 2) = 4 whenever m≥1.
Hint: Induct on m.

Answer 1

We shall prove by inducting over $m$.

When $m=1$ .

$A(1,2)=A(0,A(1,1))=A(0,2)=4.$

It is true for $m=0$.

Suppose it is true for some $m=k\geq1$ . We shall prove that it holds for $m=k+1$ .

$A(k+1,2)=A(k,A(k+1,1))\\$

Since $k\geq1, k+1\geq2$ . Hence, $A(k+1,1)=2$

So,

$A(k+1,2)=A(k,2)$

We know that it is true for $m=k$ . So, $A(k,2)=4$ .

Therefore, $A(k+1,2)=4.$

This shows that it holds for $m=k+1$ .

Hence, $A(m,2)=4$ for $m \geq1$ .