5
$\begingroup$

The Mobius inversion formula states that if we define $f$ as $$f(m)=\sum_{d|m}g(d)$$ then $$g(m)=\sum_{d|m}f\left(\frac md\right)\mu(d)$$

We know that the other direction is also true: if we define $g$ as above, then $f$ also satisfies the above.

I've searched for the proof, but failed to find any that does not rely on convolutions. My question is whether there is a proof that relies on manipulating sums that proves the second direction of the theorem.

$\endgroup$
3
  • 1
    $\begingroup$ How about just doing it? Put the second into the first, and hack away.... $\endgroup$ Jan 27, 2019 at 10:41
  • $\begingroup$ @LordSharktheUnknown not sure how I would do that, sorry $\endgroup$ Jan 27, 2019 at 10:54
  • 2
    $\begingroup$ It's kind of hard to avoid using convolutions when there's one in the problem's statement. $\endgroup$
    – jmerry
    Jan 27, 2019 at 10:57

1 Answer 1

3
$\begingroup$

We assume \begin{align*} g(m)=\sum_{d|m}f\left(\frac md\right)\mu(d)\tag{1} \end{align*} and show the validity of \begin{align*} f(m)=\sum_{d|m}g(d)\tag{2} \end{align*}

It is convenient to use the unit-function $u$ defined as $u(n)=1, n\geq 1$.

We start with the right-hand side of (2) and obtain \begin{align*} \color{blue}{\sum_{m|n}g(m)}&=\sum_{m|n}\left(\sum_{d|m}f\left(\frac {m}{d}\right)\mu(d)\right)u\left(\frac{n}{m}\right)\tag{3}\\ &=\sum_{a\cdot m=n}\left(\sum_{b\cdot d=m}f(b)\mu(d)\right)u(a)\\ &=\sum_{a\cdot b\cdot d=n}f(b)\mu(d)u(a)\\ &=\sum_{b\cdot m=n}f(b)\left(\sum_{a\cdot d=m}\mu(d)u(a)\right)\\ &=\sum_{m|n}f\left(\frac{n}{m}\right)\left(\sum_{d|m}\mu(d)u\left(\frac{m}{d}\right)\right)\\ &=\sum_{m|n}f\left(\frac{n}{m}\right)\sum_{d|m}\mu(d)\\ &=\sum_{m|n}f\left(\frac{n}{m}\right)\left\lfloor\frac{1}{m}\right\rfloor\tag{4}\\ &\,\,\color{blue}{=f(n)}\tag{5} \end{align*}

and the claim (2) follows.

Comment:

  • In (3) we use the identity (1) and multiply for convenience only with $1=u\left(\frac{n}{m}\right)$.

  • In (4) we use the identity $\sum_{d|m}\mu(d)=\left\lfloor\frac{1}{m}\right\rfloor=\begin{cases}1&m=1\\0&m>1\end{cases}$.

  • In (5) we obtain $f(n)$ since all other summands with $m>1$ in (4) give zero.

Note: We can omit the usage of $u$ in the derivation, but this might reduce readability.

$\endgroup$
1
  • 1
    $\begingroup$ @Abdrew: I will have a look at it tomorrow. Regards, $\endgroup$
    – epi163sqrt
    Oct 10, 2020 at 19:39

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.