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.


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.

  • $\begingroup$ Could you explain how you get that from changing the order $\endgroup$ – Tyler Hilton Mar 23 '13 at 2:36
  • $\begingroup$ 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$. $\endgroup$ – i707107 Mar 23 '13 at 15:49
  • $\begingroup$ Is it possible to deduce $\left| \sum_{d\leq x} \frac{\mu(d)}{d} \right| \leq 1$ $\endgroup$ – Tyler Hilton Mar 24 '13 at 23:21
  • $\begingroup$ Use $\lfloor\frac{x}{d}\rfloor=\frac{x}{d}+\{\frac{x}{d}\}$ where $\{\frac{x}{d}\}$ is the fractional part of $\frac{x}{d}$ $\endgroup$ – i707107 Mar 25 '13 at 2:35
  • $\begingroup$ Im not sure what you mean by fractional part. so [6/4] = 1 + 1/2? $\endgroup$ – 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) $$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.