Prove that $\operatorname{ack}(3,y)=2^{y+3}-3$.

Question

Prove that: $$\operatorname{ack}(3,y)=2^{y+3}-3$$ where $\operatorname{ack}$ refers to the Ackermann function.

Here's what I have so far.

This statement can be prove by induction over $y$.

Induction Start: $\operatorname{ack}(3,0)= \operatorname{ack}(2,1)=5=8-3=2^3-3=2^{0+3}-3$

Induction Assumption: The statement $\operatorname{ack}(3,y)=2^{y+3}-3$ holds for all $y \in \mathbb{N}$.

Induction Step: The statement should also hold for $y \to y +1 \in \mathbb{N}$, $\operatorname{ack}(3,y+1) = 2^{(y+1)+3}-3$.

$$\operatorname{ack}(3,y+1) = \operatorname{ack}(2, \operatorname{ack}(3,y+1-1))= \operatorname{ack}(2, \operatorname{ack}(3,y))$$

I know that I can use my induction assumption and set $\operatorname{ack}(3,y) = 2^{y+3}-3$, but I'm not able to see how I can use that to get to the final answer.

Answer 1

Let's use an "operator name" $\operatorname{ack}$ instead of $ack$.

Since $\operatorname{ack}(0,\,y)=y+1$ and $\operatorname{ack}(1,\,0)=\operatorname{ack}(0,\,1)=2$,$$\operatorname{ack}(1,\,y)=\operatorname{ack}(0,\,\operatorname{ack}(1,\,y-1))=\operatorname{ack}(1,\,y-1)+1$$for $y\ge1$, so by induction $\operatorname{ack}(1,\,y)=y+2$. Then $\operatorname{ack}(2,\,0)=\operatorname{ack}(1,\,1)=3$ and$$\operatorname{ack}(2,\,y)=\operatorname{ack}(1,\,\operatorname{ack}(2,\,y-1))=\operatorname{ack}(2,\,y-1)+2$$for $y\ge1$, so by induction $\operatorname{ack}(2,\,y)=2y+3$. Finally, $\operatorname{ack}(3,\,0)=\operatorname{ack}(2,\,1)=5$ and$$\operatorname{ack}(3,\,y)=\operatorname{ack}(2,\,\operatorname{ack}(3,\,y-1))=2\operatorname{ack}(3,\,y-1)+3$$for $y\ge1$, so by induction $\operatorname{ack}(3,\,y)=2^{y+3}-3$. I'll only make the base step explicit in this last proof by induction, as it's the hardest one: $2(2^{k+3}-3)+3=2^{k+4}-3$.