# Proving two sequences identical

I found something quite interesting while browsing around the OEIS yesterday. I have no idea how to prove this (I don't even know if it's true in general, but Mathematica tells me that it holds up to at least 50 000.) Can we prove that this sequence, that is $$\text{A095112}(n) = \sum_{\substack{p \text{ prime, } k>0 \\ p^k \mid n}} \frac{n}{p^k} \quad \overset{\underset{\mathrm{?}}{}}{=} \quad \sum_{d \mid n} \varphi(d) \Omega \left( \frac{n}{d} \right),$$ where the double sum on the left is "sum of $n/k$ over all prime powers $k>1$ which divide $n$". On the right $\varphi(n)$ denotes Euler's totient function and $\Omega(n)$ is total number of prime factors of $n$. Looking at an example we see that $$\sum_{\substack{p \text{ prime, } k>0 \\ p^k \mid 12}} \frac{12}{p^k} = \frac{12}{2} + \frac{12}{2^2} + \frac{12}{3} = 6 + 3 + 4 = 13,$$ and \begin{align*} \sum_{d \mid 12} \varphi(d) \Omega \left( \frac{12}{d} \right) &= \varphi(1)(3)+\varphi(2)(2)+\varphi(3)(2)+\varphi(4)(1)+\varphi(6)(1)+\varphi(12)(0) \\\ &= 3+2+4+2+2=13. \end{align*} How do we attack a problem like this? Is this obvious or hard? Any light shed on this would be nice!

-
Your lefthand expression doesn’t say what you want it to say: $3^2\le 12$, but $3^2\nmid 12$, so you don’t want a term $\frac{12}{9}$. You want $\sum\limits_{\substack{p\text{ prime},k>0\\p^k\mid n}}\frac{n}{p^k}$. – Brian M. Scott Nov 7 '11 at 9:43
@BrianM.Scott: I was a bit unsure about that, thanks. – Carolus Nov 7 '11 at 10:11

The identity is true. Here is a proof:

Let $*$ denote Dirichlet convolution, that is $(f*g)(n)=\sum_{d|n}f(d)g\left(\frac{n}{d}\right)$. Then let $\chi$ be the indicator function for the prime powers, that is $\chi(n)=1$ if $n=p^k$ and $\chi(n)=0$ otherwise. Notice that in particular $$(\chi*1)=\sum_{d|n}\chi(d) =\Omega(n).$$

Recall that $(\phi*1)(n)=\sum_{d|n}\phi(d)=n$. Hence we can write $$\sum_{p^k |n} \frac{n}{p^k}=\sum_{d|n} \chi(d)\frac{n}{d}=(\text{Id}*\chi)(n)=(\phi*1*\chi)(n)$$

$$=(\phi*\Omega)(n)=\sum_{d|n}\phi(d)\Omega\left(\frac{n}{d}\right)$$ as desired.

A similar proof with the indicator function for the primes rather then prime powers yields

$$\sum_{p|n} \frac{n}{p} =\sum_{d|n}\phi(d)\omega\left(\frac{n}{d}\right).$$

-
Wow, it was easier than I thought! Very nice explanation. By the way, did you see my question regarding this answer of yours? – Carolus Nov 7 '11 at 12:10
This is an old answer, but the second line should read: $(f*g)(n)=\sum_{d|n}f(\textbf{d})g\left(\frac{n}{d}\right)$ – 6005 May 15 '13 at 14:23

The key here is the formula $$\sum_{d | n} \varphi(d) = n.$$ Note that $\Omega(n/d)$ counts the number of non-trivial prime powers $p^k$ dividing $n/d$. Let $p^k|n$ where $k > 0$. How many times is $p^k$ counted in the right-hand side? It is counted $\varphi(d)$ times whenever $p^k|n/d$, which is to say, whenever $d|n/p^k$, and in total $$\sum_{d | n/p^k} \varphi(d) = \frac{n}{p^k} \text{ times}.$$ The identity immediately follows.

To answer your second question, how do we attack a problem like this, I suggest trying to understand what the two sides are counting. My solution (which is identical to Eric's) starts with an understanding of the right-hand side, and then uses a well-known formula to relate it to the left-hand side. So the second suggestion is: find out some basic information about the functions involved.

-