Suma de la función del número de divisores es igual a $\sum_{j=1}^{n} \lfloor n/j \rfloor$.

Question

Estoy tratando de probar la identidad

$$t(1) + t(2) + \cdots + t(n) = \Big\lfloor \dfrac{n}{1} \Big\rfloor + \Big\lfloor \dfrac{n}{2} \Big\rfloor + \cdots + \Big\lfloor \dfrac{n}{n} \Big\rfloor,$$

donde $t(j)$ es el número de divisores de a $j$.

Intento: El mayor poder de $k \in \{2, 3, \ldots, n\}$ que divide $n!$ está dado por

$$H_{k} := \Big\lfloor \dfrac{n}{k}\Big\rfloor + \Big\lfloor \dfrac{n}{k^{2}}\Big\rfloor + \cdots + \Big\lfloor\dfrac{n}{k^{N_{c}}}\Big\rfloor,$$

donde $N_{c}$ es el máximo entero de satisfacciones $k^{N_{c}} \leq n$. Con un poco de pensamiento, uno puede ver que

\begin{equation*} \begin{split} \Big\lfloor\dfrac{n}{1}\Big\rfloor + \Big\lfloor\dfrac{n}{2}\Big\rfloor + \cdots + \Big\lfloor\dfrac{n}{n}\Big\rfloor &= H_{2} + H_{3} + \cdots + H_{n} + \Big\lfloor\dfrac{n}{1}\Big\rfloor \\ &= H_{2} + H_{3} + \cdots + H_{n} + n. \end{split} \end{ecuación*}

Cada una de las $H_{k}$ es una cuentan en la suma de $t(1) + t(2) + \cdots + t(n)$, ya que cada una de las $t(k^{j})$ es un sumando de a $j \in \{1, 2, \ldots, N_{k}\}$, y también cada una de las $t(m)$ es un sumando, donde $m$ es un múltiplo de a $k$ menos que o igual a $n$.

Aquí es donde yo estoy un poco atascado: creo que el único otro sumando en $t(1) + t(2) + \cdots + t(n)$$1 + 1 + \cdots + 1 = n$, ya que cada una de las $t(j)$ cuenta $1$ como divisor. Mi problema es que muestra que estos son sólo los términos adicionales en $t(1) + t(2) + \cdots + t(n)$, lo que revelaría la igualdad.

Todas las sugerencias se agradece, o incluso sugerencias de una manera diferente.

Answer 1

Esto realmente ayuda a escribir $t(1)+t(2)+\dotsb+t(n)$ en un arreglo triangular:

1 + 
1 + 1 +
1 + 0 + 1 +
1 + 1 + 0 + 1 +
1 + 0 + 0 + 0 + 1 +
1 + 1 + 1 + 0 + 0 + 1 +
1 + 0 + 0 + 0 + 0 + 0 + 1 +
1 + 1 + 0 + 1 + 0 + 0 + 0 + 1 + 
1 + 0 + 1 + 0 + 0 + 0 + 0 + 0 + 1 + ...

Fila $k$ $t(k)$ escrito en una manera que indica que los números de 1 a $k$ brecha $k$. ¿Qué ves en vertical?

Como toque final, tenga en cuenta que $\lfloor n/d \rfloor$ cuenta el número de múltiplos de $d$ que no exceda $n$.

---

Ya se ha resuelto el problema, me explico arriba. Tenemos $$\sum_{k=1}^n t(k) = \sum_{k=1}^n \sum_{\substack{1 \le d \le n \\ d|k}} 1$$ y queremos intercambiar el orden de la suma. Bueno, como $k$$d$$1$$n$, agregar $1$ cada vez que $d$ divide $k$. Este es el mismo como la adición de $1$ cada vez que $k$ es un múltiplo de a $d$. Para una fija $d$, ¿cuántos múltiplos de $d$ entre $1$$n$? Precisamente, $\lfloor n/d \rfloor$ (son $d$, $2d$, $3d$, ..., $md \le n < (m+1)d$). Por lo $$\sum_{k=1}^n \sum_{\substack{1 \le d \le n \\ d|k}} 1 = \sum_{d=1}^n \sum_{\substack{1 \le k \le n\\ k = md}} 1 = \sum_{d=1}^n \Big\lfloor \frac{n}{d} \Big\rfloor$$ y la prueba está completa.

Answer 2

En aras de la exhaustividad, me gustaría señalar que esto es generalmente se hace por inducción. Buscamos mostrar que

$$\sum_{k=1}^n \tau(k) = \sum_{k=1}^n \bigg\lfloor \frac{n}{k} \bigg\rfloor.$$

Que tiene de $n=1:$ $$\tau(1) = \lfloor 1\rfloor.$$

En la inducción paso partimos de

$$\sum_{k=1}^n \tau(k) = \sum_{k=1}^n \bigg\lfloor \frac{n}{k} \bigg\rfloor.$$

para obtener

$$\tau(n+1) + \sum_{k=1}^n \tau(k) = \tau(n+1) + \sum_{k=1}^n \bigg\lfloor \frac{n}{k} \bigg\rfloor.$$

Ahora, $$\tau(n+1) = \sum_{k=1}^{n+1} \left(\bigg\lfloor \frac{n+1}{k} \bigg\rfloor - \bigg\lfloor \frac{n}{k} \bigg\rfloor\right)$$

desde

$$\bigg\lfloor \frac{n+1}{k} \bigg\rfloor - \bigg\lfloor \frac{n}{k} \bigg\rfloor = \begin{cases} 1 \quad\text{if}\quad k|n+1 \\ 0 \quad\text{otherwise}.\end{casos}$$

Por lo tanto, tenemos

$$\sum_{k=1}^{n+1} \tau(k) = \sum_{k=1}^{n+1} \left(\bigg\lfloor \frac{n+1}{k} \bigg\rfloor - \bigg\lfloor \frac{n}{k} \bigg\rfloor\right) + \sum_{k=1}^n \bigg\lfloor \frac{n}{k} \bigg\rfloor \\ = \sum_{k=1}^{n+1} \left(\bigg\lfloor \frac{n+1}{k} \bigg\rfloor - \bigg\lfloor \frac{n}{k} \bigg\rfloor\right) + \sum_{k=1}^{n+1} \bigg\lfloor \frac{n}{k} \bigg\rfloor \\ = \sum_{k=1}^{n+1} \bigg\lfloor \frac{n+1}{k} \bigg\rfloor$$

y la inducción es completa.

Answer 3

es la teoría básica de convolución de Dirichlet : $$\zeta(s) = \sum{n=1}^\infty n^{-s}$$ $% $ $\zeta(s)^2 = (\sum{n=1}^\infty n^{-s})(\sum{m=1}^\infty m^{-s} )= \sum{n=1}^\infty \sum{m=1}^\infty n^{-s} m^{-s}= \sum{n=1}^\infty n^{-s} \sum{d|n} 1 = \sum{n=1}^\infty \tau(n) n^{-s}$allí es también la fórmula de Perron : $$\sum_{n=1}^\infty an n^{-s} = \int{1-\epsilon}^\infty (\sum_{n=1}^\infty a_n \delta(x-n)) x^{-s} dx = s \int1^\infty (\sum{n \le x} a_n) x^{-s-1}dx$ $ (integración por parte)

por lo tanto

$$\zeta(s) = s \int1^\infty (\sum{n \le x}1) x^{-s-1} dx = s \int_1^\infty \lfloor x \rfloor x^{-s-1} dx$$

$$\zeta(s)^2 = s \int1^\infty (\sum{n \le x}\tau(n)) x^{-s-1} dx$$

pero también se puede escribir

$$\zeta(s)^2 = (\sum_{n=1}^\infty n^{-s} )s \int_1^\infty \lfloor x \rfloor x^{-s-1} dx = s \int1^\infty (\sum{n=1}^\infty \lfloor x/n \rfloor) x^{-s-1}dx$ $ (desde $\int_0^\infty f(x/n) x^{-s-1}dx = n^{-s} \int_0^\infty f(y) y^{-s-1}dy$ con $x= ny$)

es decir

$$\sum{n \le x}\tau(n) = \sum{n=1}^\infty \lfloor x/n \rfloor = \sum_{n \le x} \lfloor x/n \rfloor$$