Ackerman function

Question

I have a very elementary question: here

on the page 7, 4th line

why

$$ A_{k+1} (n+1) = A_k (A_{k+1} (n))$$

Is it trivial or do we need induction ?

Answer 1

It depends on the way the definition is phrased.

A common way of defining the Ackermann function is this one:

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

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

(3) $A(k+1,n+1)=A(k,A(k+1,n))$

If you rewrite $A(k,n)$ as $A_k(n)$, line (3) becomes

$A_{k+1}(n+1) = A_k(A_{k+1}(n))$

Your source uses an alternative style of definition, starting with $A_1$ and $A_{k+1}(n) = A_k\circ\cdots\circ A_k(1)=A_k^n(1)$. Starting from there, you can also obtain

$$ A_{k+1}(n+1) = A_k^{n+1}(1)= A_k(A_k^n(1)) = A_k(A_{k+1}(n)) $$