Una prueba de teoría de números combinatoria

Question

¿Cómo puedo demostrar la siguiente identidad?

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

donde $\omega(k)$ es el número de divisores primos distintos de $k$ .

Answer 1

Aquí hay una pista muy grande:

$$[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}$$

Considera la inducción...

Aplicando el operador de diferencia hacia delante a nuestra ecuación y desplazando hacia atrás, $$\sigma_0(n^2)=\sum_{d|n}2^{\omega(d)}$$ es lo que necesitamos demostrar primero para una prueba de inducción viable sobre la afirmación original. Esto se puede hacer, ya que ambos lados son funciones multiplicativas (nota $\omega(ab)=\omega(a)+\omega(b)$ cuando $a,b$ son coprimos), y en potencias primos $n=p^r$ , $$\sum_{d|n}2^{\omega(d)}=1+\sum_{l=1}^r 2^1=2r+1,$$ que está de acuerdo con $\sigma_0(p^{2r})$ .

(Sin embargo, me gustaría ver una prueba más biyectiva.)