# Prove $A(x,y)= 2[x](y+3)-3$. Where A is the Ackermann-Peter function and [x] is x-th hyperoperator.

I've successfully proven $A(x,y)$ for some fixed x and any y with induction but I'm having a hard time proving this for any x and y. I think the next useful step would be proving $A(x,0)= 2[x]3-3$ but I still having trouble proving it... The definition of $A(x,y)=$ $$\begin{eqnarray*} A(0,y) &=& y+1 \\ A(x+1,0) &=& A(x,1) \\ A(x+1,y+1) &=& A(x,A(x+1,y)) \end{eqnarray*}$$

• Perhaps you should give the definition of $A$, because there are many slightly different definitions... – Xoff Dec 20 '15 at 11:31

## 1 Answer

First, you may see that for all $x$, $2[x]2=4$ for all $x>0$

For $x=0$ $$2(y+3 )-3=y+4-3=y+1=A(0,y)$$

Now, by induction on $x$, I suppose this is true for $x$ : $A(x,y)=2[x](y+3 )-3$

For $x+1$

$$A(x+1,0)=A(x,1)=2[x]4-3=2[x](2[x]2)-3=2[x+1]3-3$$

(This is also true when $x=0$, because $A(1,0)=2=5-3=23-3$)

Now by induction on $y$ :

\begin{align} A(x+1,y+1)&=A(x,A(x+1,y))\\ &=2[x]\bigl(2[x+1](y+3 )-3+3\bigr)-3\\ &=2[x]\bigl(2[x+1](y+3 )\bigr)-3\\ &=2[x+1](y+4 )-3\\ \end{align}