9. [35] Find all positive integers $n$ such that
$$
\sum_{k=1}^{n} \phi(k)=\frac{3 n^{2}+5}{8}
$$
Answer: $1,3,5$.
Solution. We contend that the proper relation is
$$
\sum_{k=1}^{n} \phi(k) \leq \frac{3 n^{2}+5}{8}
$$

Let $\Phi(k)$ denote the left hand side of $(*)$. It is trivial to see that for $n \leq 7$ the posed inequality holds, has equality where $n=1,3,5$, and holds strictly for $n=7$. Note that $\phi(2 k) \leq k$ and $\phi(2 k+1) \leq 2 k$, the former because $2,4, \ldots, 2 k$ share a common divisor. It follows that $\phi(2 k)+\phi(2 k+1) \leq 3 k$. Suppose for the sake of induction that $\Phi(2 k-1)<\frac{3(2 k-1)^{2}+5}{8}$. Then
$$
\Phi(2 k+1)=\Phi(2 k-1)+\phi(2 k)+\phi(2 k+1)<\frac{3(2 k-1)^{2}+5}{8}+3 k=\frac{3(2 k+1)^{2}+5}{8} .
$$

To complete the proof, it is enough to note that for a positive integer $k$,
$$
\frac{3(2 k-1)^{2}+5}{8}+k<\frac{3(2 k)^{2}+5}{8} \text {. }
$$