Probar$n!$ nunca es divisible por$2^n$

Question

El problema me quiere demostrar por inducción que $n!\neq2^nk$ por cada $n$$N$. Primero de todo, he sido por lo general haciendo pruebas donde muestro algo es cierto, así que ahora estoy un poco confundida, ya no sé qué puedo aplicar el mismo enfoque (caso base, asunción, show para $n+1$) o tal vez mostrar el caso base, se asume que éste no espera, y a continuación, mostrar que esa suposición conduce a alguna contradicción para $n+1$ ?

He intentado lo siguiente. Se demostró que para $n=1\Rightarrow2\neq4k$. Suponiendo que tiene de $n$ traté de probar para $n+1$, $$(n+1)!\neq2^{n+1}k\Rightarrow(n+1)n!\neq2^n\cdot2k$$ Ahora probablemente debería utilizar el IH de alguna manera, pero no estoy seguro de cómo.

Answer 1

Por Legendre de la fórmula,

$$\nu_2(n!)=\sum_{k=1}^\infty{\left\lfloor\frac n{2^k}\right\rfloor}.$$

Pero

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

La desigualdad estricta se justifica por el hecho de que todos los términos con $2^k>n$ faltan.

---

Tenga en cuenta que el "peor caso" es al $n$ es una potencia de $2$: a continuación, $n!$ es divisible por $2^{n-1}$.

---

Inducción:

El desarrollo de la $n!$ $\lfloor n/2\rfloor$ incluso factores. Si descartas el extraño factores y dividir a todos, incluso por $2$, que al final hasta con el desarrollo de la $\lfloor n/2\rfloor$!

Por lo tanto $$ \nu_2(n!)=\a la izquierda\lfloor\frac n{2}\right\rfloor+ \nu_2\left(\left\lfloor\frac n{2}\right\rfloor !\right)$$ dar de Legendre de la fórmula por medio de la inducción. (También el uso de $\lfloor\lfloor n/2^k\rfloor/2\rfloor=\lfloor n/2^{k+1}\rfloor$.)

Answer 2

Sea$y=f(x)$ el entero mayor y tal que$2^y$ divida x.

Si$k\le2^m$ entonces$f(k)=f(2^m+k)$ que implica$f(k!)=f(\frac{(2^m+k)!}{2^m!})$

Así que si has probado que$f(k!)<2^k$ para todos$k\le 2^m$ entonces$f((2^m+k)!)=f(2^m!)f(k!)<2^{2^m}2^k=2^{2^m+k}$ así que probarlo también para m 1

Answer 3

La cuestión subyacente se pone de manifiesto al señalar lo siguiente:

(2n)! $\;$ =$\;$ (2q 1) [$2\cdot 4\cdot 6\cdot \cdots (2n-4) \cdot (2n-2)\cdot 2n$]$\;$ =$\;$$2^n \cdot$ n! (2q 1)

(2n 1)! = (2n 1) (2n)! =$2^n\cdot$ N! (2q 1) (2n 1) =$2^n\cdot$ n! (2p 1)

¡norte! $\;=\:\; 2^{k_n}$ (2m 1)

$k_1 = 0, \;k_2 = 1, \; k_3 = 1; \; k_4 = 3 \;\;$ ($k_n<n \;\;$ Todo por inspección trivial)

Una prueba por inducción entonces sigue fácilmente.