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. # 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 . Please do not write to this address regarding general admissions or course queries.