Ackermann function proof by Induction

Question

I'm currently studying discrete mathematics and i've been given an assignment to prove the following: $A(1, n) = n +2$ for all $ n \geq 0$ with induction. But i am somewhat unsure if i've done it correctly.

Ackermanns function is defined as:

• $A(0, n) = n + 1, n \geq 0$

• $A(m, 0) = A(m - 1,1) ,m > 0$

• $A(m, n) = A(m - 1, A(m, n - 1)), m, n > 0 $

Here's what i've done so far:

Base Case, $n = 0$: $A(1,0) = A(1-1, 1) = A(0,1) = 1+1 = 2$

Induction Hypothesis, $n = k$: Assume true for $A(1, k) = k + 2$, when $k \geq 0$

Prove: $n = k + 1$:

• I followed the third function because if we have $k + 1$ then $k > 0$

(1): $A(1, k + 1) = A[1-1, A(1, k+1-1)]$

• Question: Am i allowed to set $k = 0$ when proving n = k + 1?

If $k = 0$

Calculate the inner function of (1): $A(1, k+1-1) = A(1,0)$

(2): $A(1, 0) = A(1-1,1)$

Calculate function from (2): $A(1-1,1) = A(0, 1)$

(3): $A(0, 1) = 1 + 1 = 2$

Replace the inner function of (1) with the result from (3)

(1): $A(1, 0 + 1) = A(0, 2) = 2 + 1 = 3$

Answer 1

The induction is on $n$.

Your first step is correct; for $n=0$ we have that:

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

that is $n+2$ for $n=0$.

For the induction step, we have to assume that the property holds for $k$ and prove it for $k+1$.

Thus, we assume the induction hypotheses: $A(1,k)=k+2$, and we have to compute:

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

which is $n+2$ for $n=k+1$.

Answer 2

Based on ackermanns function rules : Show the following $A (1,n)=n+2$ For $n=0$

$A (1,0)=A (0,1)=1+1=2$ true

Assume $n=k$ then $A(1,k)=k+2$ its true

Proof that $n=k+1$ also true

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

$=A (0,A (1,k))$

$=A (0,k+2)$

$=(k+2)+1$

$=(k+1)+2$

Proved :))