Fix integers $n$ and $k$. Why is $\sum_{\substack{d < n\\(d, k) = 1}} \frac{\mu(d)^{2}}{\varphi(d)} \geq \sum_{\substack{d < n\\(d, k) = 1}}\frac{1}{d}?$
Arithmetic function inequality
-
1Why do you think this is true? – 2012-11-26
1 Answers
2nd try. I hope this works well.
Collect $d$'s that have prime divisors $\left\{p_1 , \cdots , p_k\right\}$.
Note that because $\mu$ is zero for non-square-free, the only surviving term on the LHS is $\frac{1}{\phi(p_1 \cdots p_k)}=\frac{1}{(p_1-1)\cdots (p_k-1)}$.
For RHS, the sum is less than $\frac{1}{p_1\cdots p_k}(1-\frac{1}{p_1})\cdots (1-\frac{1}{p_k})$.
Because $\frac{p}{p-1}>1>1-\frac{1}{p}$, we know that $LHS > RHS$ for any collection of primes $\left\{p_1 , \cdots , p_k\right\}$.
Well, now sum over the collection $\left\{p_1 , \cdots , p_k\right\}$.
Then there are many repeated terms on the RHS when we sum over $\left\{p_1 , \cdots , p_k\right\}$, of course, but that's irrelevant because each terms are positive.
Hence LHS $\geq$ RHS and equality holds only when $d=1$(i.e, there is no prime that divide some d's).