¿Cómo probar esta suma?

Question

Cómo probar esta suma, sin la inducción matemática? Muchas gracias! Yo no puedo encontrar una manera para reducir n a $\sqrt{n}$.

$$ \sum_{i=1}^{n}\left\lfloor \frac{n}{i} \right\rfloor = 2\sum_{i=1}^{\left\lfloor \sqrt{n} \right\rfloor}\left\lfloor \frac{n}{i} \right\rfloor - \lfloor \sqrt{n} \rfloor ^2 $$

---

UPD: creo que tengo una prueba, gracias a todos, especialmente a pedro idea.

sea f(n) indicar los números de n,$\sum_{i=1}^{n}\left\lfloor \frac{n}{i} \right\rfloor=\sum_{i=1}^{n}f(i)$, debido a $\left\lfloor \frac{n}{i} \right\rfloor$ puede ser visto como $i,2i...\left\lfloor \frac{n}{i} \right\rfloor i \leq n$, me múltiples, también podemos considerar el yo como un número de divisores, aparece al mismo tiempo que es $\left\lfloor \frac{n}{i} \right\rfloor$.

luego nos calcuate f(n), si $a\vert n$$\frac{n}{a}\vert n$, uno a uno, a continuación,$f(n)=2\sum_{i\leq \sqrt{n}, i\vert n}1$. Pero hay una excepción, que es cuando n es un número cuadrado, se cuentan dos veces, vamos a denotar g(n)=1 si n es un cuadrado de más g(n)=0. entonces:

$$ f(n) = 2\sum_{i\leq \sqrt{n}, i\vert n}1 - g(n) $$

así tenemos

$$ \sum_{i=1}^{n}\left\lfloor \frac{n}{i} \right\rfloor =\sum_{i=1}^{n}f(i) =\sum_{i=1}^{n}(2\sum_{j\leq \sqrt{i}, j\vert i}1 - g(i)) =2\sum_{i=1}^{n}\sum_{j\leq \sqrt{i}, j\vert i}1) - \sum_{i=1}^{n}g(i) $$

softonic subíndice cambiando y tengo:

$$ \sum_{i=1}^{n}\sum_{j\leq \sqrt{i}, j\vert i}1) =\sum_{j=1}^{\left\lfloor \sqrt{n} \right\rfloor}\sum_{i\geq j^2,j\vert i}1 =\sum_{j=1}^{\left\lfloor \sqrt{n} \right\rfloor}\sum_{k=j}^{\left\lfloor \frac{n}{j} \right\rfloor}1 =\sum_{j=1}^{\left\lfloor \sqrt{n} \right\rfloor}(\left\lfloor \frac{n}{j} \right\rfloor-j+1)\\ =\sum_{i=1}^{\left\lfloor \sqrt{n} \right\rfloor}\left\lfloor \frac{n}{i} \right\rfloor-\sum_{i=1}^{\left\lfloor \sqrt{n} \right\rfloor}(i-1) =\sum_{i=1}^{\left\lfloor \sqrt{n} \right\rfloor}\left\lfloor \frac{n}{i} \right\rfloor-\left\lfloor \sqrt{n} \right\rfloor(\left\lfloor \sqrt{n} \right\rfloor-1)/2 $$

así tenemos:

$$ 2\sum_{i=1}^{n}\sum_{j\leq \sqrt{i}, j\vert i}1) - \sum_{i=1}^{n}g(i) =2(\sum_{i=1}^{\left\lfloor \sqrt{n} \right\rfloor}\left\lfloor \frac{n}{i} \right\rfloor-\left\lfloor \sqrt{n} \right\rfloor(\left\lfloor \sqrt{n} \right\rfloor-1)/2)-\left\lfloor \sqrt{n} \right\rfloor\\ =2\sum_{i=1}^{\left\lfloor \sqrt{n} \right\rfloor}\left\lfloor \frac{n}{i} \right\rfloor - \lfloor \sqrt{n} \rfloor ^2 $$

Answer 1

Usted puede ver por qué esto es a partir de la gráfica de la hipérbola:

La suma $$\sum_{i=1}^{n}\left\lfloor \frac{n}{i} \right\rfloor$$ counts the area under this curve while the sum $$2\sum_{i=1}^{\left\lfloor \sqrt{n} \right\rfloor}\left\lfloor \frac{n}{i} \right\rfloor - \lfloor \sqrt{n} \rfloor ^2$$ cuenta el área debajo de la plaza y una de las patas de la hipérbola dos veces, luego la toma de distancia de la plaza que era el doble de contado.

---

Prueba de este aviso podemos escribir la suma como una suma de divisores $$\sum_{i \le n} d(i) = \sum_{i \le n} \sum_{d|i} 1 = \sum_{dk \le n} 1 = \sum_{i \le n}\left\lfloor \frac{n}{i} \right\rfloor$$

es la segunda y última forma en la cual se muestra la misma simetría nos dimos cuenta de que la geometría, por lo que podemos usar para probar la identidad: Acaba de dividir la suma de esta $$\sum_{dk \le n} = \sum_{\begin{array}{c}d \le \lfloor \sqrt{n} \rfloor \\ dk \le n\end{array}}+\sum_{\begin{array}{c}k \le \lfloor \sqrt{n} \rfloor \\ dk \le n\end{array}}-\sum_{\begin{array}{c}d \le \lfloor \sqrt{n} \rfloor \\ k \le \lfloor \sqrt{n} \rfloor\end{array}}$$ y ya está