Identidad que Euler ' función φ: \sum \limits_{k=1}^n \left\lfloor \frac{n}{k $} \right\rfloor \varphi(k) = \frac{n(n+1)} {2} $

Question

Deje que $\varphi(n)$ ser de Euler totient función, el número de enteros positivos menores o iguales a $n$ y relativamente primos a $n$.

Reto: Demostrar

$$\sum_{k=1}^n \left\lfloor \frac{n}{k} \right\rfloor \varphi(k) = \frac{n(n+1)}{2}.$$

Tengo dos pruebas, una de las cuales es parcialmente combinatoria.

Me estoy planteando este problema, en parte porque creo que algunas personas en este sitio estaría interesado en trabajar en él y en parte porque me gustaría ver una puramente combinatoria prueba. (Pero por favor, puesto que las pruebas; yo estaría interesado en noncombinatorial, demasiado. He aprendido mucho en este sitio por la lectura alternativa de pruebas de los resultados ya lo sé.)

Voy a esperar un par de días para dar a otros la oportunidad de responder antes de la publicación de mis pruebas.

EDIT: La de dos pruebas en total ahora se han dado entre las respuestas.

Answer 1

Un enfoque es el uso de la formula $\displaystyle \sum_{d \mediados de k} \varphi(d) = k$

Así que tenemos que $\displaystyle \sum_{k=1}^{n} \sum_{d \mediados de k} \varphi(d) = n(n+1)/2$

Intercambiando el orden de la recapitulación, podemos ver que el $\displaystyle \varphi(d)$ término aparece $\displaystyle \left\lfloor \frac{n}{d} \right\rfloor$ veces

y así

$\displaystyle \sum_{d=1}^{n} \left\lfloor \frac{n}{d} \right\rfloor \varphi(d) = n(n+1)/2$

O en otras palabras, si tenemos $n \times n$ matriz $A$ que

$\displaystyle a[i,j] = \varphi(j)$ si $j \mid i$ y $0$ lo contrario.

La suma de los elementos de la fila i $$ es $i$.

La suma de los elementos de la columna $j$ es $\displaystyle \left\lfloor \frac{n}{j} \right\rfloor \varphi(j)$ y la identidad sólo dice que la suma total por la suma de las filas es igual a la suma total por la suma de las columnas.

Answer 2

En caso de que alguien esté interesado, aquí son las versiones completas de mis dos pruebas. (I construyó la combinatoria uno de mis originales parcialmente combinatoria uno después de que envió la pregunta.)

---

La no-combinatoria prueba

Como Derek Jennings observa, $\lfloor \frac{n+1}{k} \rfloor - \lfloor \frac{n}{k} \rfloor$ es $1$ si $k|(n+1)$ y $0$ lo contrario. Por lo tanto, si $$f(n) = \sum_{k=1}^n \left\lfloor\frac{n}{k} \right\rfloor \varphi (k),$$ entonces $$\Delta f(n) = f(n+1) - f(n) = \sum_{k|(n+1)} \phi(k) = n+1,$$ donde la última igualdad se sigue de la conocida fórmula Aryabhata de la cites.

Entonces $$\sum_{k=1}^n \left\lfloor\frac{n}{k} \right\rfloor \varphi (k) = f(n) = \sum_{k=0}^{n-1} \Delta f(k) = \sum_{k=0}^{n-1} (k+1) = \frac{n(n+1)}{2}.$$

---

La combinatoria de prueba

Ambos lados contar el número de fracciones (reducible o irreducible) en el intervalo (0,1] con denominador $n$ o más pequeños.

Para el lado derecho, el número de formas de seleccionar un numerador y un denominador es el número de formas de elegir dos números con la sustitución del conjunto $\{1, 2, \ldots, n\}$. Esto es conocido por ser $$\binom{n+2-1}{2} = \frac{n(n+1)}{2}.$$

Ahora por el lado izquierdo. El número de fracciones irreducibles en $(0,1]$ con denominador $k$ es igual al número de enteros positivos menores o iguales a $k$ y primos relativos con $k$; es decir, $\varphi(k)$. Entonces, para una determinada fracción irreducible $\frac{a}{k}$, $\left\lfloor \frac{n}{k} \right\rfloor$ total de fracciones con denominadores $n$ o más pequeño en su clase de equivalencia. (Por ejemplo, si $n = 20$ y $\frac{a}{k} = \frac{1}{6}$, entonces las fracciones de $\frac{1}{6}, \frac{2}{12}$ y $\frac{3}{18}$ son los que en su clase de equivalencia.) Por lo tanto la suma $$\sum_{k=1}^n \left\lfloor\frac{n}{k} \right\rfloor \varphi (k)$$ también da la cantidad deseada.

Answer 3

Podemos utilizar la inducción.

Tenemos $ \lfloor (n+1)/k \rfloor - \lfloor n/k \rfloor = 1 $ cuando $n \equiv -1 \textrm{ mod } k,$ ($k>1$) y $0$ lo contrario. Por lo tanto

$$ \phi(1) + \sum_{k=2}^n \left( \left\lfloor \frac{n+1}{k} \right\rfloor -
\left\lfloor \frac{n}{k} \right\rfloor \right) \phi(k) = \sum_{k=1, k \textrm{ s.t. } n \equiv -1 \textrm{ mod } k}^n \phi(k)$$ $$= \sum_{ k | (n+1), k \ne n+1} \phi(k) = (n+1) - \phi(n+1),$$

usando $\sum_{d|k} \phi(d) = k.$ Así, suponiendo que el resultado es cierto para $n,$ tenemos

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

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

que, usando el resultado anterior para sustituir la suma,

$$= (n+1) + \frac{n(n+1)}{2} = \frac{(n+1)(n+2)}{2}.$$

Tomando nota de que el resultado es verdadero cuando $n=1 \textrm{ y } 2$ completa la prueba.

Answer 4

Mira el problema de contar todos los triples (d,m+1,k) donde $d\leq m\leq n$ y $mcd(d,m)=\frac{m}{k}$. Para cada uno (d,m+1) tenemos exactamente un k tal que $mcd(d,m)=\frac{m}{k}$, por lo que estamos contando exactamente todos los pares (i,j) donde $ i < j \leq n+1 $ es $\binom{n+1}{2}$.

Por otro lado, para cada k , si $ mcd(d,m)=\frac{m}{k} $, entonces $ k \a mediados de m $ y hay $ \left\lfloor \frac{n}{k}\right\rfloor $ m, y para cada m tenemos $\varphi(k)$ d que satisface esta igualdad, por lo que hay $ \left\lfloor \frac{n}{k}\right\rfloor \varphi(k) $ triples que terminan con k.

---

La idea es contar el número de maneras de elegir dos números de 1,2,...,n+1 (que es el lado derecho de la ecuación). Una vez que elija el número más grande de m+1, m opciones que es exactamente $\sum_{d\mid m} \varphi(d)$ (esto es básicamente lo Imbécil que escribió). Lo que yo quería hacer es cambiar la cuenta de acuerdo a la "relación" entre d y m, y el único que funcionó es que $\frac{m}{mcd(d,m)}=k$.

Por lo tanto, va más triples (d,m+1,k) donde $\frac{m}{mcd(d,m)}=k$ y $d\leq m\leq$ n solo significa que (d,m+1) es un par ordenado de {1,...,n} y k se decidió que el anterior.

Por otro lado, para determinados k, si $\frac{m}{mcd(d,m)}=k$ entonces $k \a mediados de m$ y hay $ \left\lfloor \frac{n}{k}\right\rfloor$ m. Para cada m, si $mcd(d,m)=m/k$ entonces $mcd(\frac{d}{m/k},\frac{m}{m/k})=gcd(\frac{d}{m}k,k)=1$ y hay $\varphi(k)$ d (porque $d\leq m$).

Así que, o cada uno de los k hay $ \left\lfloor \frac{n}{k}\right\rfloor \varphi(k) $ opciones , y sumando más de k va a dar el lado izquierdo de la ecuación.