A combinatorial number theory proof 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$.

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.)
