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