Mathematically, how does one find the value of the Ackermann function in terms of n for a given m? 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.
 A: $$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)
A: 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.
