# Restating a floor function as a finite sum

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?

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

## 1 Answer

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

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