Show that, for $n>3$, $$\sum_{k=1}^{n} \phi \left (k\right) \leq \frac{n(n+1)}{3}.$$ The hints point towards the Mobius inversion formula, but I do not see how you could use that. Any ideas?
Edit: Using the inequality obtained in this post , it would be enough to prove that $$\frac{3}{\pi^2} n^2 + n\log n + 2n + \frac{1}{2} \leq \frac{n(n+1)}{3},$$ which, according to WolframAlpha, is true for $n\geq 245$. Any other ways to arrive at this result?