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

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?

## marked as duplicate by rabota, Aaron Maroja, Gabriel Romon, Lord_Farin, John GowersMar 16 '15 at 0:42

• If $n=3$ your "identity" gives $1-1-1=-1\ne 0$. – Adam Hughes Jul 23 '14 at 4:24
• Does it? If $n = 3$ we get $$\mu(1) \cdot 3 + \mu(2) \cdot 2 + \mu(3) \cdot 1 = 3 - 2 - 1 = 0.$$ – James Pirlman Jul 23 '14 at 4:27
• Reread what you wrote, you don't have the $k$ factor in it the way you wrote it. – Adam Hughes Jul 23 '14 at 4:28
• Oh, woops, I was not paying attention. I'll fix that. – James Pirlman Jul 23 '14 at 4:29
• Ah yes, that's classical. Indeed that comes in handy, see my answer below. The last equality is from that identity. Though your example doesn't match the formula still. – Adam Hughes Jul 23 '14 at 4:30

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

• Can you explain how the third equality follows from the second a little more? Thanks. – James Pirlman Jul 23 '14 at 4:34
• Do you mean the third equality or the third line, because the third equality is just that last bit. – Adam Hughes Jul 23 '14 at 4:35
• The third equality, as in, the second double summation. I think I'm confused because I'm not really understanding your notation on the second line. What are you iterating in the summation? – James Pirlman Jul 23 '14 at 4:35
• @JamesPirlman those two designators are registering as totally separate objects to me, can you type exactly which summation you want to how it follows from the previous? – Adam Hughes Jul 23 '14 at 4:37
• Sure. I'm confused about what the summation $\sum_{dk \leq n} \mu(k)$ means, and why it is equal to $$\sum_{i=1}^n\left(\sum_{d|i} \mu(d) \right).$$ – James Pirlman Jul 23 '14 at 4:39