Upper bound for the sum of the orders in a finite group This is a cute question that I found in ML. I thought a little bit about it and couldn't complete it to a solution.

Let $G$ be a non-cyclic finite group of order $n.$ Let $S(G)=\sum_{g \in G} o(g)$ where $o(g)$ is the order of $g$ in $G.$ Prove that $S(G)<S(\mathbb{Z}/n\mathbb{Z}).$

My thoughts:
For any $d|n,$ there is a unique cyclic subgroup of $\mathbb{Z}/n\mathbb{Z}$ of order $d,$ and the number of generators of such a cyclic subgroup is $\varphi(d).$ Therefore, $S(\mathbb{Z}/n\mathbb{Z})=\sum_{d|n} \varphi(d)d.$
Let $s_d$ be the number of elements of $G$ of order $d.$ Then $S(G)=\sum_{d|n}s_dd.$ By Frobenius theorem, the number of elements $g \in G$ s.t. $g^d=1$ is a multiple of $d,$ thus $0 \leq s_d \leq dk_d$ for some non-negative integer $k_d.$  
Case 1: If for some divisor $d$ we have $dk_d=n,$ then $S(G) \leq 1+(n-1)d<1+n(n-1)/2.$
Case 2: If $dk_d \neq n$ for all divisors $d,$ then $k_d \leq \frac{n}{d}-1$ and $dk_d \leq n-d.$ Hence, $S(G) \leq \sum_{d|n}nd-d^2.$
Now we have to show that $\sum_{d|n} \varphi(d)d$ is strictly greater than the maximum of both cases 1, 2, which I couldn't prove. (I tried induction on $n,$ but it was unsuccessful!)


*

*How should one prove the inequalities?

*Is there any closed/simplified form for $\sum_{d|n} \varphi(d)d?$
Curiosity: 
What is $\lim_{n \to \infty} \frac{S(G)}{S(\mathbb{Z}/n\mathbb{Z})}?$
Added: I must confess that I came up with the last question without any thinking when I was writing the whole question, which the limit, of course, is absurd if one doesn't specify a group!
 A: This is quite a difficult problem! There are two published solutions of which I am aware. 

1)
The first is the answer to AMM 6636(ii) by F. Schmidt. (The problem proposer submitted this second part without solution!)
The citation is:
F. Schmidt, Richard Stong and John H. Lindsey. The American Mathematical Monthly , Vol. 98, No. 10 (Dec., 1991), pp. 970-972. 
Paywall: http://www.jstor.org/stable/2324168
2)
The second is in the paper whose citation is:
Amiri, H., Jafarian Amiri, S. M., & Isaacs, I. M. (2009). Sums of element orders in finite groups. Communications in Algebra, 37(9), 2978-2980. 
Paywall: http://www.tandfonline.com/doi/pdf/10.1080/00927870802502530

FYI: I became aware of these solutions in trying to figure out this MO problem. (As evidenced by the comment I left there.)
A: Answers to the two easier parts of the problem:
$f(n) = \sum_{d\mid n} d\phi(d)$ is the sum of a multiplicative function over all divisors of $n$; this is itself a multiplicative function of $n$. Thus if the prime-power factorization of $n$ is $n=p_1^{r_1}\cdots p_k^{r_k}$, we know that $f(n) = f(p_1^{r_1})\cdots f(p_k^{r_k})$. Therefore it suffices to calculate $f(p^k)$ for any prime power $p^k$, and that is not difficult: the answer is $f(p^k) = 1 + (p^{2k}-1)p/(p+1)$.
$\lim_{n\to\infty} S(G)/S(\mathbb Z/n\mathbb Z)$ doesn't exist. When $G = \mathbb Z/2\mathbb Z \times \mathbb Z/2\mathbb Z \times \mathbb Z/p\mathbb Z$ (where $p$ always denotes a prime), the ratio is $7/11$, while when $G = \mathbb Z/p\mathbb Z \times \mathbb Z/p\mathbb Z$, the ratio is $(p^3-p+1)/(p^4-p^3+p^2-p+1)$ which tends to $0$.
