12
$\begingroup$

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.

$\endgroup$
1

2 Answers 2

7
$\begingroup$

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=1$$ Then the inside summation is $\left\lfloor\frac{x}{d}\right\rfloor$. So, we are done.

$\endgroup$
6
  • $\begingroup$ Could you explain how you get that from changing the order $\endgroup$ Mar 23, 2013 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$ Mar 23, 2013 at 15:49
  • $\begingroup$ Is it possible to deduce $\left| \sum_{d\leq x} \frac{\mu(d)}{d} \right| \leq 1$ $\endgroup$ Mar 24, 2013 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$ Mar 25, 2013 at 2:35
  • $\begingroup$ Im not sure what you mean by fractional part. so [6/4] = 1 + 1/2? $\endgroup$ Mar 25, 2013 at 5:18
5
$\begingroup$

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) $$

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .