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 8

Find all functions \(f:\{1,2,3,\ldots\}\to\{1,2,3,\ldots\},\) such that for all \(n=1,2,3,\ldots\) the sum \(f(1)+f(2)+\cdots+f(n)\) is equal to a perfect cube that is less than or equal to \(n^3.\)

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

Hints

  • Hint 1
    What values can \(f(1)\) take?
  • Hint 2
    What value must \(f(1) + f(2)\) take?
  • Hint 3
    Find an expression for \(\sum_{i=1}^{n}{f(i)}\) in terms of \(n.\)
  • Hint 4
    Prove your hypothesis using induction.
  • Hint 5
    What is the value of \(f(n)\) if \(\sum_{i=1}^{n}{f(i)} = n^3\) and \(\sum_{i=1}^{n-1}{f(i)} = (n-1)^3?\)

Solution

By trying small values of \(n,\) we find that \(f(1) \leq 1^3,\) which means that necessarily \(f(1)=1.\) The next case gives us \(f(1)+f(2) = 8.\) This can give us an intuition that the function is unique: \(f(n) = n^3 - (n-1)^3.\) To prove this formally we use induction.

Let \(\Phi(n)\) be the induction hypothesis "If \(S(i)=\sum_{j=1}^i{f(j)}\) is a perfect cube less than or equal to \(i^3\) for all \(i \leq n\) then \(S(i) = i^3.\)"

Base case: \(f(1) = 1\) as it is the only perfect cube less than or equal to \(1^3,\) so \(\Phi(1)\) is true.

Inductive case: Assuming \(\Phi(k)\) is true, we can prove \(\Phi(k+1)\) as follows: Suppose \(S(i)\) is a perfect cube less than or equal to \(i^3\) for all \(i \leq k+1.\) Using the induction hypothesis \(\Phi(k)\), \(S(i) = i^3\) for all \(i \leq k.\) Since \(S(k) = k^3\) and \(S(k+1) \leq (k+1)^3,\) \(S(k+1)\) must equal \((k+1)^3\) as there are no cubes between \(k^3\) and \((k+1)^3.\) Therefore \(\Phi(k+1)\) is true.

By induction, \(S(n) = n^3\) for all \(n,\) and so \(f(n) = \sum_{j=1}^{n}{f(j)} - \sum_{j=1}^{n-1}{f(j)}\) \(= n^3 - (n-1)^3.\)

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.