# Prove $\sum_{d \leq x} \mu(d)\left\lfloor \frac xd \right\rfloor = 1$

I am trying to show $$\sum_{d \leq x} \mu(d)\left\lfloor \frac{x}{d} \right\rfloor = 1 \;\;\;\; \forall \; x \in \mathbb{R}, \; x \geq 1$$ I know that the sum over the divisors $d$ of $n$ is zero if $n \neq 1$. So we can rule out integers that are divisors of $x$ (if $x > 1$). I am not sure if I am on the right track to prove this. Any hints would be helpful. This is homework.

## 2 Answers

This is typical example in Möbius Inversion.

Use $\sum\limits_{d|n}\mu(d)=\epsilon(n)$ where $\epsilon(n)=1$ if $n=1$, and 0 otherwise. Now, $$\sum_{n\leq x}\sum_{d|n}\mu(d)=\sum_{n\leq x}\epsilon(n)=1$$ Changing the order of summation, we get $$\sum_{d\leq x}\mu(d)\sum_{d|n, n\leq x}=1$$ Then the inside summation is $\left\lfloor\frac{x}{d}\right\rfloor$. So, we are done.

• Could you explain how you get that from changing the order – Tyler Hilton Mar 23 '13 at 2:36
• The change of order works as follows: First, sum over $n$ inside instead of $d$. Then inside sum is over all multiples of $d$ but $\leq x$. That number is precisely $\lfloor\frac{x}{d}\rfloor$. – i707107 Mar 23 '13 at 15:49
• Is it possible to deduce $\left| \sum_{d\leq x} \frac{\mu(d)}{d} \right| \leq 1$ – Tyler Hilton Mar 24 '13 at 23:21
• Use $\lfloor\frac{x}{d}\rfloor=\frac{x}{d}+\{\frac{x}{d}\}$ where $\{\frac{x}{d}\}$ is the fractional part of $\frac{x}{d}$ – i707107 Mar 25 '13 at 2:35
• Im not sure what you mean by fractional part. so [6/4] = 1 + 1/2? – Tyler Hilton Mar 25 '13 at 5:18

It appears indeed to be an instance of the Moebius inversion formula, applied to $f(x) = \lfloor x \rfloor$ and $g(x) = 1$. We have $$f(x)=\sum_{d \in \mathbf{Z}, 1 \le d \le x} g(x/d).$$ Then $$g(x) = \sum_{d \in \mathbf{Z}, 1 \le d \le x} \mu(d) f(x/d)$$

• From both answers, I am confused on how the floor function is equivalent to the summation of the divisors – Tyler Hilton Mar 23 '13 at 0:22