Deje $d$ $n$ ser números enteros, con $n\geq 2$, y definir $$R(n,d) := \sum_{k\mid n} \mu( n/k)d^k,$$ where $\mu$ is the Möbius function. It can be shown (see below for an arithmetic proof) that $n\mediados de R(n,d)$. My question is whether anyone knows of a combinatorial proof of this fact? Feel free to make $d\geq 1$ si esto hace que la cuestión tiene más de combinatoria sabor.
Sketch: Supongamos $n$ tiene la primera descomposición $n = p_1^{e_1}\cdots p_r^{e_r}$. Podemos demostrar que $n\mid R(n,d)$ por inducción en $r\geq 1$. Al $r = 1$, lo $n = p^e$, uno calcula $$R(p^e, d) = d^{p^e} - d^{p^{e-1}} = d^{p^{e-1}}\left(d^{p^{e-1}(p-1)} - 1\right).$$ If $p\mediados de la d$, it's easy to see $n = p^e\mediados de la d^{p^{e-1}}$, so $n\mediados de R(n,d)$. If $p\nmid d$, then Fermat's little theorem gives that $d^{p-1} = 1 + pm$ for some $m\in \mathbb{Z}$, so $$d^{p^{e-1}(p-1)} - 1 = (1 + pm)^{p^{e-1}} - 1 = (1 + p^em') - 1 = p^em' = nm'$$ for some $m'\in \mathbb{Z}$. Esto demuestra el caso base de la inducción.
Para hacer la inducción de paso, suponga $n = ap^e$ donde $p\nmid a$, y sabes que $a\mid R(a,d)$ para todos los enteros $d$. Ahora se calcula $$R(n,d) = R(a, d^{p^e}) - R(a, d^{p^{e-1}}),$$ and hence by induction $un\mediados de R(n,d)$. On the other hand, $$R(a,d^{p^e}) - R(a,d^{p^{e-1}}) = \sum_{k\mid a}\mu(a/k)\left(d^{kp^e} - d^{kp^{e-1}}\right),$$ and every term on the right hand side is divisible by $d^{p^e} - d^{p^{e-1}}$, which in turn is divisible by $p^e$ from our work in the previous paragraph. Thus $p^e\a mediados de R(n,d)$. Since $(a,p) = 1$, it follows that $n = ap^e\a mediados de R(n,d)$, para completar la prueba.
Contexto: Al $d\geq 2$, la expresión $R(n,d)$ es el grado de la $n$-th dynatomic polinomio de cualquier polinomio mapa de $f\colon \mathbb{C}\to\mathbb{C}$ grado $d$, de modo que estas expresiones tienen algunas dinámicas de significación. Para muchos (pero no todos)$f$, $n$th dynatomic polinomio de $f$ es el polinomio cuyas raíces son exactamente las $f$-periódico puntos con el período exacto $n$. Desde estos puntos de ruptura en los ciclos de longitud $n$ bajo la dinámica de $f$, por lo tanto, sigue que el $R(n,d)$ es divisible por $n$.
