Prove $\sum_{k = 1}^n \mu(k)\left[ \frac nk \right] = 1$

Question

I need to prove the identity $$\sum_{k = 1}^n \mu(k)\left[ \frac{n}{k} \right] = 1$$ where $n$ is a natural number, and $[n]$ denotes the floor function. The proof also should not use the Möbius Inversion Formula; I'm looking for something elementary. I've tried to give a counting argument, and to give a proof using the identity $$\sum_{d|n}^n\mu(d)= 0$$ for $n > 1,$ but I haven't succeeded. What's a good way to solve this problem?

Answer 1

I guess the direct way is to write out the hyperbola summation

$$\sum_{k\le n}\mu(k)\sum_{d\le {n\over k}}1$$

$$=\sum_{dk\le n}\mu(k)$$

Now, this is all products with values $\le n$. But then this is the same as summing over all products $dk$ which are equal to each of the different integers $\le n$, hence we get:

$$=\sum_{i=1}^n\left(\sum_{dk=i}\mu(d)\right)=1+\underbrace{0+0+\ldots+0}_{n-1\text{ times}}$$

The last equality because aside from $i=1$ all the other sums on the inside are $0$ because

$$\sum_{d|n}\mu(d)=\delta(n)$$

where

$$\delta(n)=\begin{cases} 1 & n=1 \\ 0 &\text{o/w}\end{cases}$$