I was looking at a proof for the Mobius inversion formula and the first line states that


But this confuses me as it seems to imply that $F(n/d)=\sum_{d|n}f(n/d)$

But a requisite to the theorem is that $F(n)=\sum_{d|n}f(d)$

So then shouldn't we have that $F(n/d)=\sum_{d|n}f(1)$ ?

(And by that notation I mean add one f(1) to the sum for every d that divides n)


Mobius inversion formula states that if $f$ is an arithmetic function and $F(n)=\sum_{d|n}f(d)$ then $f(n)=\sum_{d|n}\mu(d)F(n/d)$

The full proof I'm looking at is found here http://mathonline.wikidot.com/the-moebius-inversion-formula

  • $\begingroup$ Could you define $f$ and $F$ for us? $\endgroup$ – Sohom Paul Jul 5 at 0:28
  • $\begingroup$ @SohomPaul edited :) $\endgroup$ – excalibirr Jul 5 at 0:31
  • 1
    $\begingroup$ There was a perfectly good answer by John Omielan, but it's been deleted. The essential content is that the quotients $n/d$, as $d$ ranges over all divisors of $n$ are exactly the same as the divisors of $n$. So the sum you have in the definition of $F$, $\sum_{d|n}f(d)$, and the sum you want, $\sum_{d|n}f(n/d)$, contain exactly the same summands, only indexed differently. $\endgroup$ – Andreas Blass Jul 5 at 1:28
  • $\begingroup$ @AndreasBlass I deleted my answer because I didn't show that either $F(n) = F(n/d)$ or, otherwise, why the equation could be adjusted as it was. I realize it's likely fairly easy to show this, but I'm leaving for now, so if & until I do figure it out, I believe it's best to leave my answer deleted. $\endgroup$ – John Omielan Jul 5 at 1:50
  • $\begingroup$ @AndreasBlass There are already several related questions here, and I didn't want to repeat their answers. Thus, I've just shown how what is being asked is equivalent to another question, which has an answer, plus is similar to another question which has $2$ answers. $\endgroup$ – John Omielan Jul 5 at 3:42

For every $d \mid n$, there is a unique corresponding $\frac{n}{d} \mid n$ since, obviously, $d \times \frac{n}{d} = n$. This means there is a $1-1$ correspondence between the elements of $d$ where $d\mid n$, and those of $\frac{n}{d}$ where $d \mid n$. Thus,

$$F(n)=\sum_{d|n}f(d)=\sum_{d|n}f(n/d) \tag{1}\label{eq1}$$

As such, with the right side of what you're asking, you get

$$\sum_{d\mid n}\mu(d)\sum_{d|n}f(n/d) = \sum_{d\mid n}\mu(d)F(n) = \sum_{d\mid n}\mu(n/d)F(n) \tag{2}\label{eq2}$$

Your left side, along with the equivalent of your right side in \eqref{eq2}, becomes

$$\sum_{d\mid n}\mu(d)F(n/d) = \sum_{d\mid n}\mu(n/d)F(n) \tag{3}\label{eq3}$$

This is specifically asked to be proven in Mobius Inversion Formula, and it has an answer. Specifically, the solution involves changing the order of summations, along with making the appropriate indices changes. Also, Understanding the proof of Möbius inversion formula asks a quite similar question, and it has $2$ answers, each of which also provide more details about changing the summation orders.

I'm somewhat surprised, and disappointed, that the Mathonline proof makes the
statement of $\sum_{d|n}\mu(d)F(n/d)=\sum_{d|n}\mu(d)\sum_{d|n}f(n/d)$ without any additional explanation. I consider it a bit questionable to do this even if the target audience were number theorists, but it's especially so for a more general audience.


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.