I am currently in the middle of the following exercise:
Exercise. Compute $$ \sum_{d|n} \left(\sigma(d)\mu\left(\frac{n}{d}\right)+\tau(d)\right),$$
where $\sigma$ is the function that corresponds to the sum of the divisors of $n$, $\mu$ is the well-known Mobius function and $\tau$ is the function that corresponds to the number of divisors of $n$.
My attempt. If we split the sum, we get the following:
$$ \sum_{d|n} \left( \sigma(d)\mu\left(\frac{n}{d}\right)\right) + \sum_{d|n} \tau(d)$$
Now, the first sum is no more than the Mobius inversion formula. Applying this, we can see that $ \sum_{d|n} \left( \sigma(d)\mu\left(\frac{n}{d}\right)\right) = n$. All we have to do now is to simplify $\sum_{d|n} \tau(d)$.
My idea for this last part was using the fact that $\tau$ is a multiplicative function. Thus, considerar $n = p_1^{a_1}\dots p_k^{a_k}$ where each $p_i$ is prime and each $a_i$ is a positive integer. My only intuition now would tell me to try to find the following formula:
$$ \sum_{k|p^a} \tau(p^a) = \sum_{i=0}^{a} (i+1)$$
Now, each divisor $d$ of $n$ is either one of the $p_i^{a_i}$ or it can also be a multiplication of some of the primes in the factorization of $n$… This seems to be quite exhaustive to do. Is there any easier way to find the formula wanted?
Thanks for any help in advance.
Best Answer
Based on @legionwhale inital idea and @GregMartin comment explaining it more carefully to me, I elaborated the following answer:
Since $\tau(d)$ is a multiplicative function, so is $g(n) = \sum_{d|n} \tau(d)$. Therefore, since we can decompose any natural number $n$ in its prime factorization, i.e., $n = p_1^{a_1}\dots p^{a_k}_k$ (where each $p_i$ is prime and each $a_i$ is a positive integer) we might conclude the following:
$$ g(n) = g(p_1^{a_1}\dots p^{a_k}_k) = g(p_1^{a_1})\dots g(p_k^{a_k})$$ And thus, all we have to do is to find the formula for $g(p^a)$, where (again) $p$ is a prime and $a$ is some natural number. Obviously, the divisors of $p^a$ is no more than the set $\{p^0, p, \dots, p^a\} = \{1,p,\dots,p^a\}$. Knowing this, we can find a formula for $g(p^a)$ using the following:
$$ g(p^a) = \sum_{d|n} \tau(p^a) = \sum_{i=0}^a \tau(p^i) = \sum_{i=0}^a (i+1) = \frac{1}{2}(a+1)(a+2). $$
Taking this into account, we now can elaborate a formula for $g(n)$, with the information I wrote at the start. Doing so,
$$ g(n) = g(p_1^{a_1})\dots g(p_k^{a_k}) = \frac{1}{2}(a_1+1)(a_1+2)\dots\frac{1}{2}(a_k+1)(a_k+2) = \frac{1}{2^k}\prod_{i=1}^k(a_i+1)(a_i+2)$$.