Demostrar que $2^n$ no divide $n!$

Question

Quiero demostrar que la $2^n$ no divide $n!$.

Yo estaba tratando por inducción y estoy confundido acerca de si lo que estoy haciendo es lo correcto.

Primero pruebo con $n=1$. De hecho: $$2^1 \nmid 1!$$

Así que si puedo tomar el I. H. como $2^n \nmid n!$, y trato de demostrarlo para $n+1$: $$2^{n+1} \nmid (n+1)!$$ $$2^{n} \cdot 2 \nmid (n+1) \cdot n!$$

Como $2^n \nmid n!$ debe ser ese $2^n$ divide $n+1$, por lo que tengo que demostrar que no es así. Si puedo probar por inducción una vez más, debo tener $n>1$ para que sea verdadera:

$$P(n) = 2^n \nmid n+1$$ $$P(n+1) = 2^n \cdot 2 \nmid n+1+1$$ pero $2^n \nmid n+1$ $2^n \nmid 1$ debido a $n>1$

Así que mi pregunta es, obviamente, si esto es correcto. Estoy dudando porque la excepción que tengo que hacer con $n$ siendo mayor que 1 para la segunda parte. Si he cometido un error podría apuntar a mí en una dirección mejor? Estoy seguro de que debe haber una manera más sencilla de probar esto.

Gracias!

Answer 1

La máxima potencia de $2$ que se divide $n!$ $$v_2(n!)=\lfloor \frac n2 \rfloor+\lfloor \frac n4 \rfloor +\cdots=\sum_{i=1}^{\infty} \lfloor\frac n{2^i}\rfloor$$

Estamos obligados desde arriba con una caída de la función del suelo para ver que $$v_2(n!)<n\sum_{i=1}^{\infty} \frac 1{2^i}=n$$

Answer 2

Por el teorema de Legendre $$\nu_2(n!) = \sum_{m\geq 1}\left\lfloor\frac{n}{2^m}\right\rfloor\leq \sum_{m\geq 1}\frac{n}{2^m}=n. $$ La igualdad puede mantener sólo si $2^k\parallel n$, pero en tal caso, el $(k+1)$-th términos de la central de sumas cumplir una desigualdad estricta.

Answer 3

Una prueba por inducción va a ser difícil porque, como $n$ incrementos, $2^n$ agrega un factor de $2$ mientras que $n!$ puede agregar muchos.

La manera en que yo lo haría es el uso de Legendre del teorema, aquí establecidas, por ejemplo: http://www.cut-the-knot.org/blue/LegendresTheorem.shtml

Si $p$ es un número primo, y $v_p(n!)$ es el exponente de el mayor poder de la $p$ dividiendo $n!$, así $p^{v_p(n!)} \mid n!$ y $p^{v_p(n!)+1} \not\mid n!$, entonces $v_p(n!) =\sum_{k=1}^{\lfloor \log_p n \rfloor} \lfloor \dfrac{n}{p^k} \rfloor $.

De ello se sigue que

$\begin{array}\\ v_p(n!) &=\sum_{k=1}^{\lfloor \log_p n \rfloor} \lfloor \dfrac{n}{p^k} \rfloor\\ &\le\sum_{k=1}^{\lfloor \log_p n \rfloor} \dfrac{n}{p^k} \\ &=n\sum_{k=1}^{\lfloor \log_p n \rfloor} \dfrac{1}{p^k} \\ &<n\sum_{k=1}^{\infty} \dfrac{1}{p^k} \qquad\text{(here is where we get a strict inequality)}\\ &=n\dfrac{\frac1{p}}{1-\frac1{p}}\\ &=\dfrac{n}{p-1}\\ \end{array} $

En particular, para $p=2$, $v_2(n!) < n $, así $2^n \no\mediados de n! $.

Tenga en cuenta que si $n=p^m$ para algunos entero $m$, entonces

$\begin{array}\\ v_p(n!) &=v_p((p^m)!)\\ &=n\sum_{k=1}^{\lfloor \log_p n \rfloor} \dfrac{1}{p^k}\\ &=n\sum_{k=1}^{m} \dfrac{1}{p^k}\\ &=p^m\dfrac{\frac1{p}-\frac1{p^{m+1}}}{1-\frac1{p}}\\ &=p^m\dfrac{1-\frac1{p^{m}}}{p-1}\\ &=\dfrac{p^m-1}{p-1}\\ \end{array} $

Si $p=2$, $v_2((2^m)!) =2^m-1 $, por lo que este pierde solo por $1$, así que $2^{2^m-1} \mid (2^m)!$ y $2^{2^m} \not\mid (2^m)!$.

Answer 4

El error en tu trabajo es la conclusión de que si $2^n | j * k$, entonces cualquiera de las $2^n | j$ o $2^n | k$. Por ejemplo, considere la posibilidad de que el 8 divide $12*6 = 72$ pero ninguno de 12 o 6 es divisible por 8.

Answer 5

Como se señaló en las otras respuestas, podemos escribir la potencia máxima de $2$ que divide $n!$$\nu_2(n!) = \sum_{k\geq 0}\left\lfloor\frac{n}{2^k}\right\rfloor$. Podemos dar una interpretación sencilla de este número, trabajando en binario. El binario de expansión de $n$$n = \sum_{k\geq 0} a_k 2^k$$a_k\in\{0,1\}$. El uso de este nos encontramos con

$$\matrix{\nu_2(n!) &=& \sum_{k\geq 0}\left\lfloor\sum_{i\geq 0} a_i 2^{i-k}\right\rfloor \\= \sum_{k\geq 0}\sum_{i\geq k} a_i 2^{i-k} &=& \sum_{k\geq 0} a_k(1+2+4+\ldots + 2^{k-1}) \\= \sum_{k\geq 0} a_k(2^k-1) &=& n - \sum_{k\geq 0} a_k}$$

Así

$$\nu_2(n!) = n - s_2(n)$$

donde $s_2(n)$ es la suma de los dígitos binarios de $n$. Si $n>0$, entonces el binario de expansión de $n$ debe contener al menos un "$1$" por lo $\nu_2(n!) < n$ sigue. El valor mínimo de $s_2(n)$ $n>0$ se produce si $n$ es en la forma $2^k$ que $s_2(n) = 1$$v_2(n!) = n-1$.