4
$\begingroup$

I feel that this is a very stupid question to be asking, but I can't figure it out. I've been trying to figure out the Möbius inversion formula, with pretty much no experience in this direction at all, and ran into the following problem:

So according to the Möbius inversion formula, $$g(n)=\sum_{d|n}f(d) \Longleftrightarrow f(n)=\sum_{d|n}g\left(\frac nd\right)\mu(d)$$. Yes? Since this is an equivalence, it should work both ways. Let's say $g(n)=1$, in that case, plug it into the right-hand formula and find that $f(n)=0$, or at least Wikipedia tells me that $\sum_{d|n}\mu(d)=0$. Problem: when we look at the formula on the left, we see that $g(n)$ is now equal to the sum of a finite number of zeros, even though we defined it as $1$. What stupid mistake am I making here?

$\endgroup$
7
  • 2
    $\begingroup$ $\sum_{d\mid n} \mu(d) = 0$ for $n > 1$. But $\sum_{d\mid 1} \mu(d) = 1$. $\endgroup$ – Daniel Fischer Jul 16 '14 at 21:37
  • $\begingroup$ Yes, but $n$ is not necessarily $1$, I think; it's the definition of $f(n)$, for $n \in \mathbb N$, so why should $n$ be restricted to $1$? $\endgroup$ – Laertes Jul 16 '14 at 21:39
  • $\begingroup$ But $$f(1) = \sum_{d\mid 1} g\left(\frac{1}{d}\right)\mu(d) = g(1)\mu(1) = g(1) = 1.$$ For $n > 1$, you have $f(n) = 0$. $\endgroup$ – Daniel Fischer Jul 16 '14 at 21:40
  • $\begingroup$ $f(n)$ is a function, it changes depending on $n$. So when $n=1$ you get $1$, only otherwise do you get $0$. $\endgroup$ – Adam Hughes Jul 16 '14 at 21:40
  • $\begingroup$ But $g(n)$ is supposed to be $1$ for all $n$. $\endgroup$ – Laertes Jul 16 '14 at 21:43
2
$\begingroup$

The point is that

$$\sum_{d\mid n} \mu(d) = \begin{cases} 1 &, n = 1\\ 0 &, n > 1. \end{cases}$$

Thus, for $g \equiv 1$ you have

$$f(n) = \sum_{d\mid n} g\left(\frac{n}{d}\right)\mu(d) = \sum_{d\mid n} \mu(d) = \begin{cases} 1 &, n = 1\\ 0 &, n > 1 \end{cases}$$

and hence

$$g(n) = \sum_{d\mid n} f(d) = f(1) + \sum_{\substack{d\mid n\\ d > 1}} f(d) = f(1) + \sum_{\substack{d\mid n\\ d > 1}} 0 = f(1) = 1,$$

as it should be.

$\endgroup$

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.