5
$\begingroup$

How can I prove the following identity:

$\sum_{k=1}^{n}{\sigma_{\ 0} (k^2)} = \sum_{k=1}^{n}{\left\lfloor \frac{n}{k}\right\rfloor \ 2^{\omega(k)}}$

where $\omega(k)$ is the number of distinct prime divisors of $k$.

  • 0
    @h$k$ju: http://en.wikipedia.org/wiki/Divisor_function2012-04-26

1 Answers 1

5

Here is a very big clue:

$[k|m]=\left\lfloor\frac{m}{k}\right\rfloor-\left\lfloor\frac{m-1}{k}\right\rfloor=\begin{cases}1 && k|m \\ 0 && \text{otherwise}.\end{cases}$

Consider induction...

Applying the forward difference operator to our equation and shifting back, $\sigma_0(n^2)=\sum_{d|n}2^{\omega(d)}$ is what we need to prove first for a workable induction proof on the original claim. This can be done, since both sides are multiplicative functions (note $\omega(ab)=\omega(a)+\omega(b)$ when $a,b$ are coprime), and on prime powers $n=p^r$, $\sum_{d|n}2^{\omega(d)}=1+\sum_{l=1}^r 2^1=2r+1,$ which agrees with $\sigma_0(p^{2r})$.

(Wish I could see a more bijective proof though. Drats.)