Prove that $1\cdot f(1)+ 2\cdot f(2)+ ...+ n\cdot f(n) \leq n(n+1)(2n+1)/6$ where $f(n+1) = f(f(n))+1$ Consider checking function $\mathbb{N}\to \mathbb{N}$ relationship $f(n+1) = f(f(n))+1$, for any positive integer $n$.
 Prove that $1\cdot f(1)+ 2\cdot f(2)+ ...+ n\cdot f(n) \leq n(n+1)(2n+1)/6$ for any positive integer $n$.

Since $1\cdot 1+ 2\cdot 2+ \cdots + n\cdot n = n(n+1)(2n+1)/6$, it is enough to prove that $f(n)\le n$, for all $n$.
We shall prove that $f(n)\le n$ for all $n$, by full induction.
Assume $f(m)\le m$ for all $m\le n$. Let's prove that $f(n+1) \le n+1$.
Let $m=f(n) \le n$. Then $f(f(n))=f(m) \le m=f(n)$.
So, $f(n+1) = f(f(n))+1 \le f(n)+1 \le n+1$.
All that remains is the base of induction: $f(1)\le 1$.
