# Ackermann function property for positive $n$

Ackermann's function is:

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

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

$A(x+1,y+1)= A(x,A(x+1,y)$

which is a total computable function but not a primitive recursive one. Why is the following property valid?

$A(n,2)= 2n+3 ,\forall n>0$

Proving that $A(n,1)= n+2 ,\forall n>0\$ is trivial, but with $n=2$ it gets a bit tricky.

My idea so far:

$A(2,n) = A(1,A(2,n-1))=A(1,A(1,A(2,n-2)))= \dots A(1,A(1,A(1,A(1\dots A(2,n-n)))))$ ,

which will give $A(2,0)= A(1,1)= A(0,A(1,0))= A(0,A(0,1)=A(0,2)=3$

and then start computing back all the way to $A(2,n)$. Alas, I cannot extract that $2n$ from this recursion.

Extra: is there any way to create a more general formula for $x = 1,2, \dots k$ for $A(k,n)$?

## 1 Answer

You do it by induction. $A(2,0)=A(1,1)=1+2=3=2\cdot 0 +3$ is the base case. Now assume $A(2,k)=2k+3$. Then $A(2,k+1)=A(1,A(2,k))=A(2,k)+2=2k+3+2=2(k+1)+3$ and we have proven for all $n, A(2,n)=2n+3.$ It is better to write this as $A(2,n)=2(n+3)-3$ to fit the pattern with higher first indices.

A similar induction works for any given value of the first index. We have $A(3,0)=A(2,1)=5=2^3-3$. We claim $A(3,n)=2^{n+3}-3.$ The base case fits. Then again assume $A(3,k)=2^{k+3}-3$. We have $A(3,k+1)=A(2,A(3,k))=2\cdot ((A(3,k)+3)-3=2\cdot(2^{k+3}-3)+6-3=2^{(k+1)+3}-3$

As the index gets higher we need another notation to express what is going on. The nicest version I know is Knuth's up-arrow notation. If I recall correctly,in terms of that, for $x \ge 3$ we have $A(x,y)=2\uparrow^{x-2}(y+3)-3.$ You can prove that by induction on $x$. The base case is $A(3,y)$ which we have shown works.

• thank you!!! now i get it – Mario Zelic May 23 '18 at 15:23