4
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ If $n=3$ your "identity" gives $1-1-1=-1\ne 0$. $\endgroup$ – Adam Hughes Jul 23 '14 at 4:24
  • $\begingroup$ Does it? If $n = 3$ we get $$\mu(1) \cdot 3 + \mu(2) \cdot 2 + \mu(3) \cdot 1 = 3 - 2 - 1 = 0.$$ $\endgroup$ – James Pirlman Jul 23 '14 at 4:27
  • $\begingroup$ Reread what you wrote, you don't have the $k$ factor in it the way you wrote it. $\endgroup$ – Adam Hughes Jul 23 '14 at 4:28
  • $\begingroup$ Oh, woops, I was not paying attention. I'll fix that. $\endgroup$ – James Pirlman Jul 23 '14 at 4:29
  • 1
    $\begingroup$ 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. $\endgroup$ – Adam Hughes Jul 23 '14 at 4:30
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Can you explain how the third equality follows from the second a little more? Thanks. $\endgroup$ – James Pirlman Jul 23 '14 at 4:34
  • $\begingroup$ Do you mean the third equality or the third line, because the third equality is just that last bit. $\endgroup$ – Adam Hughes Jul 23 '14 at 4:35
  • $\begingroup$ 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? $\endgroup$ – James Pirlman Jul 23 '14 at 4:35
  • $\begingroup$ @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? $\endgroup$ – Adam Hughes Jul 23 '14 at 4:37
  • $\begingroup$ 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).$$ $\endgroup$ – James Pirlman Jul 23 '14 at 4:39

Not the answer you're looking for? Browse other questions tagged or ask your own question.