Mathematically, how does one find the value of the Ackermann function in terms of n for a given m?

Question

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.

Answer 1

$$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)

Answer 2

From the definition of the Ackerman function, we have

\begin{align*} A(3, n) &= A(2, A(3, n - 1)) \end{align*}

Now $A(2, b)$ can be computated (at least from the table of values) to be $2b + 3$, so we find

$$A(3, n) = 2A(3, n - 1) + 3$$

This gives a recursive sequence; calling $A(3, n) = x_n$, we have the relationship

$$x_n = 2x_{n - 1} + 3$$ This can be solved directly (using, of course, an initial condition) or by substituting the guess from the pattern; either way, it's what you wrote.

---

Now all I did was transfer the problem to a different row of the table. Let's study $A(2, n)$ in the same way: We have

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

From the table, we have that $A(1, b) = b + 2$, giving the recursion

$$y_n = y_{n - 1} + 2$$ This gives exactly the solution $y_n = 2n + 3$, when we figure out the initial condition.

---

But again, this has the same problem: I just used a different previously known row. Let's do this once more:

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

But now we're in luck. By definition $A(0, b) = b = 1$, so

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

This is an easy recurrence to solve. The condition $A(1, 0) = 1$ gives us the base, and we find

$$\boxed{A(1, n) = n + 1}$$

---

So now let's put it all together, just backwards. We get $A(1, n)$ almost directly from the definition of the Ackermann function. Then we get $A(2, n)$ from a recurrence relation that reduced $A(2, n)$ to studying $A(1, A(2, n - 1))$. Then we can get $A(3, n)$ from a similar process.