I've been struggling with the following claim without being able to prove it, so your help would be highly appreciated:
Let $\varphi(n)$ be Euler's totient function. Show that there is a constant $0
I've been struggling with the following claim without being able to prove it, so your help would be highly appreciated:
Let $\varphi(n)$ be Euler's totient function. Show that there is a constant $0
We have that
$\sum_{k=1}^{n} \frac{\varphi(k)}{k} \ge \sum_{k=1}^{n} \left(\left[\frac{n}{k}\right]\frac{k}{n}\right)\frac{\varphi(k)}{k}$
$ = \frac{1}{n} \sum_{k=1}^{n} \left[\frac{n}{k}\right]\varphi(k) = \frac{n+1}{2} $
Thus you can choose $K = \frac{1}{2}$.
The last step uses the identity:
$\sum_{k=1}^{n} \left[\frac{n}{k}\right]\varphi(k) = \frac{n(n+1)}{2} $
and the first inequality uses $\left[\frac{n}{k}\right] \le \frac{n}{k}$, where $[x]$ gives the integer part of $x$.
Multiple proofs of the last identity can be found here: Identity involving Euler's totient function: $\sum \limits_{k=1}^n \left\lfloor \frac{n}{k} \right\rfloor \varphi(k) = \frac{n(n+1)}{2}$