Probando $\frac{n^n}{3^n} < n! < \frac{n^n}{2^n}$ se mantiene por inducción

Question

Soy informático y estoy intentando reforzar un poco mis conocimientos matemáticos. Esto no es una tarea y no tengo un profesor al que pueda acudir para pedir ayuda. Espero que este sea un foro apropiado para este tipo de preguntas.

Para saber más sobre las pruebas inductivas, estoy leyendo el artículo de la Wikipedia sobre ellas. Sin embargo, tengo problemas para resolver uno de los ejemplos de la página:

$$P(n) :\quad \frac{n^n}{3^n} < n! < \frac{n^n}{2^n} .$$ Prueba $P(n) \; \forall n \in \mathbb{N}, n \ge 6$

Esto es lo que he hecho hasta ahora, con el "???" indicando donde no sé el siguiente paso.

Caso base: $$\begin{array}{rrcccl} P(6)\colon& \frac{6^6}{3^6} &<& 6! &<& \frac{6^6}{2^6}\\ \iff& 2^6 &<& 6! &<& 3^6\\ \iff& 64 &<& 720 &<& 729 \end{array}$$

Paso inductivo:

$$\begin{array}{rrccclc} P(n+1) \colon&\frac{(n+1)^{n+1}}{3^{n+1}} &<& (n+1)! &<& \frac{(n+1)^{n+1}}{2^{n+1}}\\ \iff& \frac{(n+1)^{n+1}}{3^{n+1}} &<& (n+1)n! &<& \frac{(n+1)^{n+1}}{2^{n+1}} &\text{Defn factorial}\\ \iff& \frac{(n+1)(n+1)^n}{3 \cdot 3^n} &<& (n+1)n! &<& \frac{(n+1)(n+1)^n}{2 \cdot 2^n} &\{a^{m+n} = a^m a^n\}\\ \iff& \frac{(n+1)^n}{3 \cdot 3^n} &<& n! &<& \frac{(n+1)^n}{2 \cdot 2^n} &\text{Divide by n+1}\\ ??? \end{array}$$

Tal vez esto parezca una tontería sin remedio desde el punto de vista de los matemáticos, pero estoy tratando de aprender.

En concreto, lo que busco es una orientación para llegar a la respuesta por mi cuenta, o bien indicaciones sobre la documentación que debería leer para ampliar mis conocimientos.

Answer 1

Como cuestión de estilo, yo empezaría con $P(n)$ y a partir de ahí tratar de demostrar $P(n+1)$ . Esto hace que sea algo menos complicado manipular correctamente las desigualdades.

Así que si tenemos $$\frac{n^n}{3^n} < n! < \frac{n^n}{2^n},$$ cómo se consigue $P(n+1)$ ? Multiplicando por $n+1$ era un buen instinto: $$\frac{(n+1)n^n}{3^n} < (n+1)! < \frac{(n+1)n^n}{2^n}.$$ Ahora hay dos piezas que tenemos que probar: $$\frac{(n+1)^{n+1}}{3^{n+1}} < \frac{(n+1)n^n}{3^n}$$ y $$\frac{(n+1)n^n}{2^{n}} < \frac{(n+1)^{n+1}}{2^{n+1}}.$$

Aquí tienes una pista para estas dos desigualdades: $\left(1+\frac{1}{n}\right)^n$ es una función creciente (demuéstrelo) que está limitada por debajo por $2$ (cuando $n=1$ ) y converge a $e$ . Avísame si quieres algo más explícito.

Answer 2

Usted tiene dos desigualdades a demostrar. Debes demostrarlas por separado . Es posible que se duplique la escritura, pero la ganancia de claridad lógica merecerá la pena.

Dejemos que $P(n)$ sea la afirmación de que $n!<\frac{n^n}{3^n}$ . Queremos demostrar que $P(n)$ se mantiene para $n \ge 6$ .

Un cálculo menor se ocupa del caso base $n=6$ . Ahora me gustaría demostrar que si $P(n)$ se mantiene cuando $n=k$ , donde $k$ es un número entero $\ge 6$ entonces $P(n)$ se mantiene cuando $n=k+1$ . Por desgracia, ha elegido un ejemplo en el que este "paso de inducción" es menos fácil que en muchos otros casos.

Así que asumimos que sabemos que $k! <\dfrac{k^k}{2^k}$ . Queremos demostrar que $(k+1)!< \dfrac{(k+1)^{k+1}}{2^{k+1}}.$

¿Cómo podemos aprovechar nuestros conocimientos sobre $k!$ para obtener información sobre $(k+1)!$ ? Parece claro que debemos tratar de aprovechar la relación entre $k!$ y $(k+1)!$ . Desde $(k+1)!=k!(k+1)$ y sabemos que $k! < \frac{k^k}{2^k}$ tenemos $$(k+1)!<(k+1)\frac{k^k}{2^k}.$$ Si pudiéramos demostrar que $(k+1)\dfrac{k^k}{2^k} <\dfrac{(k+1)^{k+1}}{2^{k+1}}$ estaríamos acabados. Un poco de álgebra muestra que "todo" lo que tenemos que hacer es mostrar que $k^k<\dfrac{(k+1)^k}{2}$ o, lo que es lo mismo, que $\frac{(k+1)^k}{k^k}>2$ . Reescribe esto como el más familiar $\left(1+\frac{1}{k}\right)^k>2$ .

La experimentación con la calculadora parece mostrar que la desigualdad requerida es efectivamente cierta para todos los $k>1$ . Pero necesitamos probar al menos para $k \ge 6$ . ¿Inducción alguien? Utilizaremos otra herramienta.

Recordemos que por el Teorema del Binomio, $$(1+x)^k =1+\binom{k}{1}x+\binom{k}{2}x^2 +\binom{k}{3}x^3+ \cdots +\binom{k}{k}x^k.$$ Poner $x=\frac{1}{k}$ . Los dos primeros términos de la expansión binomial de $\left(1+\frac{1}{k}\right)^k$ son $1$ y $k(1/k)$ . Ya suman $2$ . Si $k>1$ los términos restantes nos sitúan por encima de $2$ . Con esto termina la prueba.

Un argumento similar muestra que la otra desigualdad también es válida. Al final tenemos que demostrar que $\left(1+\frac{1}{k}\right)^k <3$ lo cual es algo más difícil que demostrar que $\left(1+\frac{1}{k}\right)^k >2$ . Hay varias formas de manejar esa desigualdad. Una forma es demostrar (por inducción) que $\left(1+\frac{1}{k}\right)^k <3-\frac{1}{k}$ . Extrañamente, esto resulta ser más fácil que la desigualdad más débil $\left(1+\frac{1}{k}\right)^k <3$ .

Comentario: Ten en cuenta que el hecho de que no hayas podido sacar adelante el argumento no significa que no sepas de qué va la inducción. En tu problema, la demostración de las desigualdades requeridas no es obvia. Puedes probar con ejemplos estándar más sencillos, como el hecho de que $1^2+2^2+\cdots+n^2=\dfrac{n(n+1)(2n+1)}{6}$ .

Answer 3

Para el Paso Inductivo:

Supongamos que que tenemos

$$ \frac{n^n}{3^n} < n! $$ y $$ n! < \frac{n^n}{2^n}. $$

Queremos demostrar que esto implica que

$$ \frac{(n+1)^{n+1}}{3^{n+1}} < (n+1)! $$ y $$ (n+1)! < \frac{(n+1)^{n+1}}{2^{n+1}}. $$

Bajo estos supuestos, para ver que la primera desigualdad se cumple, escribe: $$\begin{align} \frac{(n+1)^{n+1}}{3^{n+1}} &= \frac{(n+1)}{3} \frac{(n+1)^n}{3^n} \\ &= \frac{n+1}{3} \left(\frac{n+1}{n}\right)^n \frac{n^n}{3^n} \\ &< \frac{n+1}{3} \left(\frac{n+1}{n}\right)^n n! \qquad (\text{using inductive hypothesis}) \\ &= \left( 1 + \frac{1}{n} \right)^n \frac{1}{3} (n+1)! \end{align}$$ y esto se reduce a demostrar que $$ \left( 1 + \frac{1}{n} \right)^n \frac{1}{3} < 1. $$ La otra desigualdad puede tratarse de forma similar. Probablemente puedas ahorrar algo de papel si haces las dos desigualdades al mismo tiempo, pero si estás empezando, te sugiero que trabajes con una desigualdad a la vez.