cómo probar $n! \mid \prod_{k=0}^{n-1}(2^n-2^k) :\forall n \in \mathbb N$?

Question

cómo probar $$n! \mid \prod_{k=0}^{n-1}(2^n-2^k) :\forall n\in \mathbb N $$

Gracias de antemano

Answer 1

Este es el bonito, ruta escénica Qiaochu menciona en los comentarios. No es totalmente obvio para mí que esto no es la "intención" de respuesta de este, ya que es etiquetado como un concurso problema.

Deje ${\bf F}_q$ denotar el (único) de campo finito con exactamente $q=p^s$ elementos ($p$ un número primo). El invertible lineal de mapas en el espacio vectorial ${\bf F}_q^n$ están en bijection con la orden de $n$-tuplas de la linealmente independiente de vectores columna de ${\bf F}_q^n$. El número de estos (así, en efecto, el tamaño de ${\rm GL}_n({\bf F}_q)$) puede ser contado de forma combinatoria, directamente.

Para el primer vector, podemos elegir lo que es distinto de cero, lo que hace de $q^n-1$ opciones posibles. Para el segundo, podemos elegir cualquier cosa que no está en el lineal lapso de la primera, y la lineal lapso de la primera vector unidimensional subespacio (así, en particular, ha $q$ elementos), por lo tanto, hay $q^n-q$ opciones posibles para el segundo vector. Podemos seguir de esta manera para

$$|{\rm GL}_n({\bf F}_q)|=(q^n-1)(q^n-q)(q^n-q^2)\cdots(q^n-q^{n-1})=\prod_{k=0}^{n-1}(q^n-q^k).$$

Otra manera de expresar esto es lo $(q-1)^nq^{(n-1)n/2}[n]_q!$ el uso de la $q$-factorial.

El grupo simétrico $S_n$ es realizado directamente como un subgrupo de ${\rm GL}_n({\bf F}_q)$ a través de matrices de permutación, y así por Lagrange del teorema se sigue que, para cualquier potencia principal $q$,

$$n!\mid\prod_{k=0}^{n-1}(q^n-q^k).$$

Este caso es, en particular,$q=2$.

Una mayoría equivalente línea de razonamiento es visto a través de acciones del grupo en Thomas' comentario: el grupo simétrico $S_n$ actúa sobre el conjunto de la $n$-tuplas de vectores linealmente independientes de a ${\bf F}_q^n$ a través de permutating las coordenadas; en ninguno de estos $n$-tuplas son dos coordenadas de la misma, por lo que cada estabilizador es trivial, por lo que cada órbita tiene el tamaño de $|S_n|=n!$ (por órbita-estabilizador), de modo que todo el espacio de $n$-tuplas bajo consideración tiene el tamaño de un múltiplo de $n!$ como es un discontinuo de la unión de las órbitas de tamaño $n!$.

Esto es bastante dejar que el subgrupo $S_n$ actuar en ${\rm GL}_n({\bf F}_q)$ a través de derecha-multiplicación por matrices inversas.

Answer 2

Una prueba directa usaría recordar cómo hemos demostrado que la potencia máxima de un primer $p$ que divide $n!$ es:

$$\sum_{k=1}^{\infty}\left\lfloor \frac{n}{p^k}\right\rfloor$$

La misma lógica puede mostrar que el mayor poder de un extraño prime que divide el lado derecho es por lo menos:

$$\sum_{k=1}^\infty\left\lfloor \frac{n}{p^{k}-p^{k-1}}\right\rfloor$$

Esencialmente, esto es debido a que $p^k$ divide $2^m-1$ al $m$ es un múltiplo de a $p^k-p^{k-1}=\phi(p^k)$.

Desde $p^k-p^{k-1} < p^k$, cada término es por lo menos tan grande como el término de la suma de $n!$

A continuación, sólo tiene que lidiar con el caso de $p=2$.