0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Does it help to notice that $\phi(k)\le k/2$ for even $k$? $\endgroup$ – Gerry Myerson Apr 27 '18 at 6:40
  • $\begingroup$ Nope, the estimate is too high then. An interesting thing to notice, though, is that for $k$ even, $$\phi(k) + \phi(k+1) + \phi(k+2) \leq \frac{2}{3}(k + k+1 + k+2) = 2(k+1).$$ But you can't really use this, since you can't split the numbers into consecutive triplets such that each triplet contains 2 even numbers. $\endgroup$ – Tanny Sieben Apr 27 '18 at 7:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.