[proofplan]
We verify the inversion identity by direct computation: substitute the definition of $g$ into the sum $\sum_{d \mid n} \mu(d) g(n/d)$, swap the order of summation, and collapse the inner sum using the fundamental Möbius identity $\sum_{d \mid m} \mu(d) = \mathbb{1}_{\{m = 1\}}$. The second form of the inversion, summing $\mu(n/d) g(d)$, follows by the substitution $d \mapsto n/d$, which is a bijection on the set of divisors of $n$.
[/proofplan]
[step:Substitute the definition of $g$ and swap the order of summation]
We are given functions
\begin{align*}
f &: \mathbb{N} \to \mathbb{C}, \\
g &: \mathbb{N} \to \mathbb{C}, \quad g(n) = \sum_{d \mid n} f(d),
\end{align*}
where all sums range over positive divisors. Substituting the definition of $g(n/d)$ into the target expression,
\begin{align*}
\sum_{d \mid n} \mu(d) \, g\!\left( \frac{n}{d} \right) = \sum_{d \mid n} \mu(d) \sum_{e \mid n/d} f(e).
\end{align*}
The double sum ranges over pairs $(d, e)$ with $d \mid n$ and $e \mid n/d$. Equivalently, the pair $(d, e)$ satisfies $de \mid n$ — because $e \mid n/d$ iff $de \mid n$, and conversely if $de \mid n$ then setting $d$ as chosen divisor gives $e \mid n/d$.
Swapping the order: first fix $e$, then sum over $d$. The condition $de \mid n$ with $e$ fixed is equivalent to $d \mid n/e$ (and implicitly $e \mid n$). So
\begin{align*}
\sum_{d \mid n} \mu(d) \sum_{e \mid n/d} f(e) = \sum_{e \mid n} f(e) \sum_{d \mid n/e} \mu(d).
\end{align*}
The finite double sum (only finitely many divisors of $n$) permits the interchange without convergence issues.
[guided]
Our goal is to compute $\sum_{d \mid n} \mu(d) g(n/d)$. The plan is to expand $g$ by its definition, swap the order of the resulting double sum, and recognise a standard identity in the inner sum.
Unpacking the definition:
\begin{align*}
\sum_{d \mid n} \mu(d) g\!\left( \frac{n}{d} \right) = \sum_{d \mid n} \mu(d) \sum_{e \mid n/d} f(e).
\end{align*}
The pair $(d, e)$ ranges over those satisfying $d \mid n$ and $e \mid n/d$. We describe this set differently. If $d \mid n$ and $e \mid n/d$, then $n/d = em$ for some $m$, so $n = dem$, i.e., $de \mid n$. Conversely, if $de \mid n$ (with $d, e \geq 1$), then $d \mid n$ (since $d \mid de$ and $de \mid n$), and $n/d$ is divisible by $e$, so $e \mid n/d$. Thus
\begin{align*}
\{(d,e) : d \mid n, \, e \mid n/d\} = \{(d,e) : de \mid n\}.
\end{align*}
This symmetric description suggests we can swap the summation order. Instead of fixing $d$ first and then ranging over $e$, fix $e$ first and range over $d$. The condition $de \mid n$ with $e$ fixed imposes $e \mid n$ (for there to be any valid $d$) and, given this, is equivalent to $d \mid n/e$. So
\begin{align*}
\sum_{d \mid n} \mu(d) \sum_{e \mid n/d} f(e) = \sum_{e \mid n} \sum_{d \mid n/e} \mu(d) f(e) = \sum_{e \mid n} f(e) \sum_{d \mid n/e} \mu(d).
\end{align*}
We have pulled $f(e)$ out of the inner sum because it does not depend on $d$. No convergence subtleties arise because the sums are finite (the number of divisors of $n$ is finite).
[/guided]
[/step]
[step:Apply the fundamental Möbius identity $\sum_{d \mid m} \mu(d) = \mathbb{1}_{\{m = 1\}}$]
The inner sum $\sum_{d \mid m} \mu(d)$ for $m = n/e$ is evaluated by the Möbius identity: for $m \geq 1$,
\begin{align*}
\sum_{d \mid m} \mu(d) = \begin{cases} 1 & \text{if } m = 1, \\ 0 & \text{if } m > 1. \end{cases}
\end{align*}
Denoting this function by $\nu(m) := \sum_{d \mid m} \mu(d) = \mathbb{1}_{\{m = 1\}}$, we have
\begin{align*}
\sum_{e \mid n} f(e) \sum_{d \mid n/e} \mu(d) = \sum_{e \mid n} f(e) \, \nu\!\left( \frac{n}{e} \right).
\end{align*}
The factor $\nu(n/e)$ is nonzero only when $n/e = 1$, i.e., when $e = n$. Thus only the term $e = n$ contributes, giving
\begin{align*}
\sum_{e \mid n} f(e) \, \nu\!\left( \frac{n}{e} \right) = f(n) \cdot \nu(1) = f(n) \cdot 1 = f(n).
\end{align*}
Combining with Step 1,
\begin{align*}
\sum_{d \mid n} \mu(d) \, g\!\left( \frac{n}{d} \right) = f(n),
\end{align*}
which is the first form of the Möbius inversion.
[guided]
The inner sum $\sum_{d \mid n/e} \mu(d)$ is a classical object. The Möbius identity states that
\begin{align*}
\nu(m) := \sum_{d \mid m} \mu(d) = \begin{cases} 1 & m = 1, \\ 0 & m \geq 2. \end{cases}
\end{align*}
This is the content of the [Fundamental Möbius Identity](/theorems/???); we recall why it holds. For $m = 1$, the only divisor is $1$, and $\mu(1) = 1$. For $m \geq 2$, write $m = p_1^{a_1} \cdots p_k^{a_k}$ with $k \geq 1$ distinct primes and $a_j \geq 1$. The only divisors $d$ with $\mu(d) \neq 0$ are the squarefree divisors $d = \prod_{j \in T} p_j$ for subsets $T \subseteq \{1, \ldots, k\}$, and for such $d$, $\mu(d) = (-1)^{|T|}$. Thus
\begin{align*}
\nu(m) = \sum_{T \subseteq \{1, \ldots, k\}} (-1)^{|T|} = \prod_{j=1}^k (1 - 1) = 0.
\end{align*}
Applying this identity with $m = n/e$,
\begin{align*}
\sum_{d \mid n/e} \mu(d) = \nu\!\left( \frac{n}{e} \right) = \mathbb{1}_{\{n/e = 1\}} = \mathbb{1}_{\{e = n\}}.
\end{align*}
Substituting,
\begin{align*}
\sum_{e \mid n} f(e) \, \nu\!\left( \frac{n}{e} \right) = \sum_{e \mid n} f(e) \, \mathbb{1}_{\{e = n\}}.
\end{align*}
The indicator picks out the single term $e = n$ from the sum, and the sum collapses:
\begin{align*}
\sum_{e \mid n} f(e) \mathbb{1}_{\{e = n\}} = f(n).
\end{align*}
Combining with Step 1,
\begin{align*}
\sum_{d \mid n} \mu(d) g\!\left( \frac{n}{d} \right) = f(n).
\end{align*}
This is the first form of the Möbius inversion formula: we have recovered $f$ from $g$ by convolving with $\mu$.
[/guided]
[/step]
[step:Obtain the second form by the involution $d \leftrightarrow n/d$ on divisors of $n$]
The map
\begin{align*}
\sigma : \{d \in \mathbb{N} : d \mid n\} &\to \{d \in \mathbb{N} : d \mid n\} \\
d &\mapsto n/d
\end{align*}
is a bijection of the set of divisors of $n$ to itself (it is involutive: $\sigma \circ \sigma = \operatorname{id}$). Applying the substitution $d' = n/d$ to the first form,
\begin{align*}
f(n) = \sum_{d \mid n} \mu(d) \, g\!\left( \frac{n}{d} \right) = \sum_{d' \mid n} \mu\!\left( \frac{n}{d'} \right) g(d'),
\end{align*}
where we used $d = n/d'$ so that $\mu(d) = \mu(n/d')$ and $g(n/d) = g(d')$, and the index $d'$ ranges over divisors of $n$ precisely when $d$ does. Renaming $d' \to d$,
\begin{align*}
f(n) = \sum_{d \mid n} \mu\!\left( \frac{n}{d} \right) g(d).
\end{align*}
This is the second form.
Combining the two identities from this step and Step 2,
\begin{align*}
f(n) = \sum_{d \mid n} \mu(d) \, g\!\left( \frac{n}{d} \right) = \sum_{d \mid n} \mu\!\left( \frac{n}{d} \right) g(d),
\end{align*}
which is the claimed Möbius inversion formula.
[guided]
We have established
\begin{align*}
f(n) = \sum_{d \mid n} \mu(d) g\!\left( \frac{n}{d} \right).
\end{align*}
The theorem also asserts the equivalent form $f(n) = \sum_{d \mid n} \mu(n/d) g(d)$; this is a reindexing.
Consider the map $\sigma : d \mapsto n/d$ on the divisors of $n$. If $d \mid n$, then $n/d$ is a positive integer that also divides $n$ (since $d \cdot (n/d) = n$ and $d$ is a positive divisor). Applying $\sigma$ twice returns us to $d$: $\sigma(\sigma(d)) = \sigma(n/d) = n/(n/d) = d$. So $\sigma$ is an involution on the divisor set, and in particular a bijection.
In the sum $\sum_{d \mid n} \mu(d) g(n/d)$, apply the substitution $d' = n/d$, equivalently $d = n/d'$. As $d$ ranges over divisors of $n$, so does $d'$. Under the substitution:
\begin{align*}
\mu(d) \to \mu(n/d'), \qquad g(n/d) = g(d').
\end{align*}
So
\begin{align*}
\sum_{d \mid n} \mu(d) g\!\left( \frac{n}{d} \right) = \sum_{d' \mid n} \mu\!\left( \frac{n}{d'} \right) g(d').
\end{align*}
Renaming the summation variable to $d$ (this is a purely cosmetic relabelling),
\begin{align*}
f(n) = \sum_{d \mid n} \mu\!\left( \frac{n}{d} \right) g(d).
\end{align*}
This is the second form in the theorem statement. The two forms are equivalent: one summing "$\mu$ at $d$, $g$ at $n/d$", the other "$\mu$ at $n/d$, $g$ at $d$" — and the involution $d \leftrightarrow n/d$ translates between them.
[/guided]
[/step]
