Looking at the Wikipedia page, there's the table of values for small function inputs. I understand how the values are calculated by looking at the table, and how it's easy to see that 5,13,29,61,125 is $2^{n+3}-3$, but how does one go about calculating this "iterative" formula without pattern identification?
I started by looking at 61 (Ackermann 3,3) as being $2*(2*(2*(2*1+3)+3)+3)+3$
, which all I'm doing is expanding the recursive formula, but I have no idea that's simplified to create $2^{n+3}-3$ rather than just looking at patterns. This is not homework, just curiosity.
Best Answer
$$A(0,n) = n+1 \;\text{(by definition)}$$
$$A(1,n) \rightarrow A(0,A(1,n-1)) \rightarrow A(1,n-1)+1 \rightarrow A(1,n-2)+2\Rightarrow A(1,0)+n$$ $$\rightarrow A(0,1)+n \rightarrow 2+n = \color{red}{2+(n+3)-3}$$
$$A(2,n) \rightarrow A(1,A(2,n-1)) \rightarrow A(2,n-1)+2 \rightarrow A(2,n-2)+4 \Rightarrow A(2,0)+2n$$ $$\rightarrow A(1,1)+2n \rightarrow 2n+3 = \color{red}{2(n+3)-3}$$
$$A(3,n) \rightarrow A(2,A(3,n-1)) \rightarrow 2(A(3,n-1)+3)-3 \rightarrow 4(A(3,n-2)+3)-3 $$ $$\Rightarrow 2^n(A(3,0)+3)-3 \rightarrow 2^n(A(2,1)+3)-3 = 2^n(2^3)-3 = \color{red}{2^{n+3}-3} $$
$$A(4,n) \rightarrow A(3,A(4,n-1)) \rightarrow 2^{A(4,n-1)+3}-3 \rightarrow 2^{2^{A(4,n-2)+3}}-3 \rightarrow 2^{2^{2^{A(4,n-3)+3}}}-3 $$ $$\Rightarrow\,(^{n}2)^{A(4,0)+3}-3 \rightarrow (^{n}2)^{A(3,1)+3}-3 \rightarrow (^{n}2)^{2^3}-3 \,=\, \color{red}{{^{n+3}}2-3}$$
$$\text{Assume}\;A(m,n) = 2[m](n+3)-3,\; \text{and note} \;2[m]2=4 \;\forall m>0$$ $$A(m+1,0) \rightarrow A(m,1) \rightarrow 2[m]4-3 = 2[m](2[m]2)-3 = \color{red}{2[m+1]3-3}$$ $$A(m+1,n+1) \rightarrow A(m,A(m+1,n)) \rightarrow 2[m](2[m+1](n+3)-3+3)-3\\ = 2[m](2[m+1](n+3))-3 = \color{red}{2[m+1](n+4)-3}$$ $$\mathbf{QED}$$
Note: single right arrow represents a single iteration of Ackermann function, and a double arrow represents many (usually $n$ iterations)