Answer to Question #148112 in Discrete Mathematics for Promise Omiponle

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(1, n) = 2^n whenever n≥1.
Hint: Induct on n.

Answer 1

We shall prove by inducting over $n$.

When $n=1$ .

$A(1,1)=2=2^1.$

We see that it is true for $n=1$.

Suppose it is true for some $n=k\geq1$ . That is, $A(1,k)=2^k$ .

We shall prove that it holds for $n=k+1$ . Since $k\geq1 \implies k+1\geq2$ .

So,

$A(1,k+1)=A(1-1,A(1,k+1-1))\\ A(1,k+1)=A(0,A(1,k))\\$

Recall that $A(1,k)=2^k$ .

$\implies A(1,k+1)=A(0,2^k)=2.2^k=2^{k+1}$ .

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

This shows that it is true for $n=k+1$ . Hence, $A(1,n)=2^n$ whenever $n\geq1$ .