Prueba de la desigualdad $n! \geq 2^n$ por inducción

Question

Tengo dificultades para resolver un ejercicio en mi curso.

La pregunta es:

Demuestra que $n! \geq 2^n$ .

Tenemos que hacer esto con la inducción. Yo empecé así:

1. El número natural más bajo donde la suposición es correcta es $4$ como: $4! \geq 2^4 \iff 24 \ge 16$ .
2. La suposición es: $n! \ge 2^n$ .

Ahora la prueba para $(n+1)$ lo que me lleva a: $(n+1)! \ge 2^{(n+1)}$

Creo que puedo reescribirlo de alguna manera así:

$$ {(n+1)} \times {n!} \stackrel { \text {(definition of factorial)}}{ \ge } 2^n \times 2 $$

$$ (n+1) \times 2^n \ge 2^n \times 2 $$

Entonces creo que puedo eliminar el $2^n$ y tener algo como esto: $n+1 \ge 2$ o $n \ge 1$ .

Pero creo que me equivoqué en algún punto y esperaba que alguien me diera algún consejo sobre esto. ¿Cómo puedo probar la suposición anterior?

Cualquier ayuda sería apreciada, saludos cordiales.

Answer 1

En el paso de inducción quieres mostrar que si $k! \ge 2^k$ para algunos $k \ge 4$ Entonces $(k+1)! \ge 2^{k+1}$ . Como ya sabes que $4! \ge 2^4$ el principio de inducción matemática le permitirá entonces concluir que $n! \ge 2^n$ para todos $n \ge 4$ . Tienes todas las piezas necesarias; sólo tienes que juntarlas adecuadamente. Específicamente, puedes argumentar lo siguiente.

Supongamos que $k! \ge 2^k$ donde $k \ge 4$ Esta es su hipótesis de inducción. Entonces $$ \begin {align*} (k+1)! &= (k+1)k! \text { (by the definition of factorial)} \\ & \ge (k+1)2^k \text { (by the induction hypothesis)} \\ &> 2 \cdot2 ^k \text { (since }k \ge 4 \text {)} \\ &= 2^{k+1}. \end {align*}$$ Esto completa el paso de inducción: muestra que si $k \ge 4$ Entonces $$k! \ge 2^k \implies (k+1)! \ge 2^{k+1}.$$

Answer 2

Voy a proporcionar una forma diferente de hacerlo esto es esencialmente la prueba de Brian M. Scott a la inversa. Como la gente ha señalado, si puedes mostrar que $n! > 2^n$ entonces habrás demostrado que $n! \geq 2^n$ (en este sentido, puedes pensar en $>$ como más fuerte que $ \geq $ porque $>$ implica $ \geq $ ).

Cuando se considera $n! \geq 2^n$ y cómo te atascaste tratando de trabajar de izquierda a derecha para probar el argumento por inducción, puede ser conveniente en algunos casos trabajar de derecha a izquierda ya que $n! \geq 2^n$ es exactamente lo mismo que $2^n \leq n!$ . Con esto en mente, daré una pequeña prueba de que $2^n < n!$ para $n \geq 4$ (como dije, es muy similar a la de Brian, pero proporciona una forma diferente de hacerlo, sin embargo, que puede ser útil para usted u otros en el futuro).

---

Para $n \geq 4$ denotan la declaración que involucra $n$ por $$ S(n) : 2^n<n!. $$ Paso base ( $n=4$ ): Desde $2^4=16$ y $4!=24$ la declaración $S(4)$ es cierto.

Paso inductivo: Arreglar algunos $k \geq 4$ y asumir que $$ S(k) : 2^k < k! $$ es cierto. Lo que se demuestra es que $$ S(k+1) : 2^{k+1} < (k+1)! $$ sigue. Comenzando con el lado izquierdo de $S(k+1)$ , \begin {alinear} 2^{k+1} &= 2(2^k) \\ [0.5em] &< 2(k!) \tag {\a6}*Por $S(k)$ } \\ [0.5em] &< (k+1)(k!) \tag Desde que $k \geq 4$ } \\ [0.5em] &= (k+1)!, \end {alinear} el lado derecho de $S(k+1)$ . Esto concluye el paso inductivo $S(k) \to S(k+1)$ .

Así, por inducción matemática, para todos $n \geq 4$ la desigualdad $S(n)$ es cierto.