I've learned the Ackermann Function in my CS class but the formula looks a bit off compared to the ones I see on Wikipedia or other websites. The formula I learned was:
$$f(k,1)=2,$$ $$f(1,n)=n+2, n>1,$$ $$f(k,n)=f(k-1,f(k,n-1)), k,n>1$$ But the one I see online is, $$A(m,n)= \begin{cases} n+1,& m= 1\\ A(m-1,1), & m>0, n=0\\ A(m-1, A(m,n-1)), &m,n>0 \end{cases}$$ The last lines of both of these formulas are essentially the same but what about the two above? Also I tried to find the Ackermann Function for $f(2,n)$. Based on my first formula I get the following: $$f(2,n)=f(1,f(2,n-1))$$ $$f(2,n-1)=f(1,f(2,(n-1)-1))$$ $$f(2,n-2)=f(1,f(2,n-3))$$ I can see the pattern, where the it's always $(n-1)-1$ but the answer key states that it's $2n$. I've looked high and low for the answer but I can't find anything. Help is appreciated.
The horrible truth is that there is no single "Ackermann's function".
There's a (for lack of a better word) family of possible Ackermann's-functions. They all share the central recursion equation for the general case -- which is what make them grow fast -- but differ in how the boundary conditions are set up.
Each author who wants to presents "Ackermann's function" will choose boundary conditions that makes it easy to prove the particular properties he's interested in. (Or some authors will instead choose the simplest boundary conditions that actually make the function grow). This results in different functions that just share the property of growing faster than is possible for a primitive recursive function.
In the case of your particular exercise, the way to go about it is to give each $f(k,{-})$ its own name -- so you would have, for example $g(n)=f(1,n)$ satisfying the definion $$ g(n) = \begin{cases} 2 & \text{if }n=1 \\ n+2 & \text{otherwise} \end{cases} $$ and then $h(n)=f(2,n)$ with $$ h(n) = \begin{cases} 2 & \text{if }n=1 \\ g(h(n-1)) & \text{otherwise} \end{cases} $$ It is easy to see that $h(n)>1$ always, so in the second line of this we can unfold the appropriate part of the definition og $g$ to give $$ h(n) = \begin{cases} 2 & \text{if }n=1 \\ h(n-1)+2 & \text{otherwise} \end{cases} $$ Hopefully it is clear that this actually outputs $2n$.