En $\lfloor\sqrt n \rfloor+ \sum_{j=1}^n \lfloor n/j\rfloor$

Question

¿Cómo demostramos que $\Big[\sqrt n \Big]+ \sum_{j=1}^n \bigg[ \dfrac nj\bigg]$ es un número entero par para todo $n \in \mathbb N$ ? (donde $\Big[ \space \Big]$ denota la función "mayor número entero")

Answer 1

$\left[\frac{n}{j}\right]$ es el número de enteros positivos $k$ tal que $k\cdot j \leqslant n$ . Así

$$\sum_{j=1}^n \left[\frac{n}{j}\right] = \sum_{j\cdot k \leqslant n} 1 = \sum_{m = 1}^n \left(\sum_{j\cdot k = m} 1\right) = \sum_{m=1}^n \tau(m),$$

donde $\tau(m)$ es el número de divisores de $m$ . Todo número entero positivo que no sea un cuadrado perfecto tiene un número par de divisores, mientras que un cuadrado perfecto tiene un número impar de divisores. Hay $\left[\sqrt{n}\right]$ cuadrados perfectos $\leqslant n$ . Por lo tanto

$$\sum_{j=1}^n \left[\frac{n}{j}\right] \equiv \left[\sqrt{n}\right] \pmod{2}.$$