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

## Related topics

## Hints

- Hint 1What values can \(f(1)\) take?
- Hint 2What value must \(f(1) + f(2)\) take?
- Hint 3Find an expression for \(\sum_{i=1}^{n}{f(i)}\) in terms of \(n.\)
- Hint 4Prove your hypothesis using induction.
- Hint 5What 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.[email protected]. Please do not write to this address regarding general admissions or course queries.