The CSAT and Practice[+] are designed by the Climb Foundation to help candidates. We are advocates for more opportunity to shine and less opportunity to fail, and we strive to level the playing field.

The Computer Laboratory

Practice Paper 4 Question 7

The function \(f\) is defined recursively for all integers \(n>1,p>0\) as follows: \[ \begin{align} f(1,p) &= C + p, \\ f(n,1) &= C, \\ f(n,p) &= f(n-1, f(n,p-1)) \end{align} \] 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.

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

Hints

  • Hint 1
    Try writing out and spotting patterns in \(f(2,p).\)
  • Hint 2
    Try writing this in a non-recursive form.
  • Hint 3
    ... by noticing it is only recursive in the second argument, \(p\) (the \(2\) is fixed).
  • Hint 4
    How might you do the same for \(f(3,p)?\)
  • Hint 5
    Remember to use results you've already shown.

Solution

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.\)

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.foo[email protected]. Please do not write to this address regarding general admissions or course queries.