# Simple Divisor Summation Inequality (with Moebius function)

Show that

$$\left| \sum_{k=1}^{n} \frac {\mu(k)}{k} \right| \le 1$$

where $\mu$ is Moebius function and n is a positive integer.

The hard thing here is that the sum is not directly divisor sum; it's just a normal summation. What I know is that when $F(n)=\sum_{d|n}f(d)$,

$$\sum_{k=1}^N F(k)=\sum_{k=1}^N f(k)\left[\frac{N}{k}\right]$$

But it was hardly useful since the given inequality doesn't contain the Guass function, so it became really complicated(and I'm not very confident in using the doulbe-summation). One thing I also know is that

$$\frac{\phi(n)}{n}=\sum_{d|n}\frac{\mu(d)}{d}$$

I also tried to use this using Moebius Inversion Formula, but it also became quite complicated. For example, we can derive that

$$\frac{\mu(k)}{k}=\sum_{d|k}\frac{\phi(d)}{d} \mu \left(\frac{k}{d}\right)$$

I couldn't make it more compact. So by substitution, we get

$$\sum_{k=1}^{n} \frac {\mu(k)}{k}=\sum_{k=1}^{n}\sum_{d\mid k}\frac{\phi(d)}{d} \mu \left(\frac{k}{d}\right)$$

If it were not for the $k$ in the right term of Moebius function, we could use the first lemma I'd written down, but we can't. So I'm just stuck.

Could anybody help me solving this problem? It would be really grateful if someone could also give me general methods to tackle divisor-sum problems since I'm having a difficult time in changing the order of doulbe-summations.

Thanks!

Let $e(k)=\sum_{d|k}\mu(d)$ and $s(n)=\sum_{k=1}^{n}e(k)$ , Then we have $$s(n)=\sum_{k=1}^n\mu(k)\left\lfloor\frac{n}{k}\right\rfloor$$ and $$\left|\sum_{k=1}^n\mu(k)\left\lfloor\frac{n}{k}\right\rfloor-n\sum_{k=1}^n\frac{\mu(k)}{k}\right|\leq\sum_{k=1}^n|\mu(k)|\left|\left\lfloor\frac{n}{k}\right\rfloor-\frac{n}{k}\right|\leq\sum_{k=1}^{n-1}|\mu(k)|\leq n-1$$ Hence, $$\left|n\sum_{k=1}^n\frac{\mu(k)}{k}\right|\leq(n-1)+|s(n)|=(n-1)+1=n$$ and $$\left|\sum_{k=1}^n\frac{\mu(k)}{k}\right|\leq1.$$