It seems to me that a floor function can be expressed as a finite sum that is open to the Möbius function.

Does it follow for all nonnegative integers $a$ that:

$$\left\lfloor\frac{a}{b}\right\rfloor = \sum_{b\mid n}^{n\le a} 1$$

If this is true, how would one prove it?

If it is not true, what would be a counter example?

  • 3
    $\begingroup$ This is correct, but the divisibility goes the wrong way to apply Möbius inversion. $\endgroup$ – Slade Mar 5 '15 at 1:17
  • 1
    $\begingroup$ Wouldn't the application of the Möbius inversion be something like this. $\endgroup$ – Larry Freeman Mar 5 '15 at 1:41
  • $\begingroup$ Color me surprised, then. I hadn't seen that particular trick before. $\endgroup$ – Slade Mar 5 '15 at 1:55

Here$\let\leq\leqslant\let\geq\geqslant\newcommand\and{\text{ and }}$ is one way to see why the equality holds, but this approach does not involve the Möbius-function.
$\sum_{b\mid n}^{n\leq a} 1$ counts the number of multiples of $b$ that are less than or equal to $a$. Let's write and rewrite this property in a symbolic way:

$$n\leq a\and b\mid n\iff n\leq a\and n=kb\text{ for some }k\iff k\leq\frac ab\and n=kb\text{ for some }k.$$

So we're counting the number of integers $n$ for which $n=kb$ and $k\leq\frac ab$. Clearly, every such $n$ corresponds to a unique such $k$, so counting the number of $k$'s for which $$k\leq\frac ab$$ is exactly the same question as counting the number of $n$ satisying the said condition.

There are exactly $\left\lfloor\frac ab\right\rfloor$ such $k$.

  • $\begingroup$ Thanks! That's exactly the answer that I was looking for! $\endgroup$ – Larry Freeman Mar 10 '15 at 23:33

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.