The function $f$ is defined recursively for all integers $n>1,p>0$ as follows: \begin{aligned} f(1,p) &= C + p, \\ f(n,1) &= C, \\ f(n,p) &= f(n-1, f(n,p-1)) \end{aligned} where $C>0$ is a real constant. Give a non-recursive expression for $f(4,p).$ Proof is not required. Hint: You may want to try $f(2,p)$ first.

Try writing out and spotting patterns in $f(2,p).$

Try writing this in a non-recursive form.

… by noticing it is only recursive in the second argument, $p$ (the $2$ is fixed).

How might you do the same for $f(3,p)?$

Remember to use results you’ve already shown.

Using the hint provided in the question, we try to find an expression for $f(2,p).$ From the definition we get that $f(2,p) = f(1, f(2, p-1)) = C + f(2, p-1).$ Since the first argument is fixed at $2,$ we can unravel it to get $f(2,p)=C+\ldots+C+f(2,1)=C \cdot p.$

We can apply the same strategy to find $f(3,p).$ We start with $f(3,p) = f(2, f(3, p-1)),$ at which point we use our previous result to get $f(3,p)=C \cdot f(3,p-1).$ Similarly, this unravels to $f(3,p)=C^p.$

Finally, we get to $f(4,p) = f(3, f(4, p-1)) = C^{f(4,p-1)},$ which expands to $f(4, p) = C^{C^{\cdot^{\cdot^{\cdot^C}}}},$ which is a tower of height $p.$