Question

One version of Ackermann’s function A(m,n) is defined recursively for m, n ∈ N by:
Bitmap
A(0, n)= n + 1, n ≥ 0;
A(m, 0) = A(m − 1, 1), m > 0; and
A(m, n) = A(m − 1, A(m, n − 1)), m, n > 0.

a. Calculate A(1, 3) and A(2, 3).
b. Prove that A(1, n) = n + 2 for all n ∈ N.
c. For all n ∈ N show that A(2, n) = 3 + 2n
d. Verify that A(3, n) = 2n+3 − 3 for all n ∈ N.

Answer 1

@Mertsj @hartnn

Answer 2

@Zarkon