Prueba por la inducción que $2^n \gt n^k$

Question

¿Cómo pruebo usando inducción eso si $k$ es un número natural, entonces el $2^n \gt n^k$ % todo $n \geq k^2 + 1$, donde $n$ también es un número natural?

Answer 1

Si se encuentra sólo en esta prueba, que es bastante engorroso. Yo hoppe que yo no cometen el error existe y que alguien va a venir para arriba con una solución más elegante.

---

Lema 1: $2^k\ge k^2$ cualquier $k\ge 4$.

EDIT: En los comentarios se puede encontrar un buen argumento combinatorio proporcionada por Aryabhata, que trabaja por $k\ge5$.

Prueba por inducción: $1^\circ$ $k=4$ la igualdad se mantiene.

$2^\circ$ Supongamos que el lema se tiene para $k$. Para $k+1$ tenemos

$2^{k+1}=2.2^k \ge \left(\frac{k+1}k\right)^2. k^2 = (k+1)^2$

(desde $\frac{k+1}k =1+\frac1k \le \frac 54 \le \sqrt 2$)

Lema 2: $\left(1+\frac1{k^2}\right)^k < 2$ $k\ge 2$.

Sabemos que $\left(1+\frac1{k^2}\right)^{k^2} < 3$ (ver aquíy aquí, usted puede encontrar esto en muchos de los libros de texto introductorios de cálculo), lo que significa que $\left(1+\frac1{k^2}\right)^k < 3^{1/k} \le 2$.

---

Reclamo: Si $n=k^2+t$ para algún entero positivo $t$ $k\ge 2$ a continuación,$2^n>n^k$.

Inducción en $t$. $1^\circ$ $t=1$ . Si $k\ge 4$, luego tenemos a $2^k\ge k^2$ $\Rightarrow$ $2^{k^2}\ge(k^2)^k$. Si multiplicamos esta desigualdad por $2>\left(\frac{k^2+1}{k^2}\right)^k$, lo que sabemos del Lema 2, obtenemos $2^n>n^k$. Para $k=2,3$ podemos verificar esto con la mano.

$2^\circ$ Supongamos que $n=k^2+t+1$, y que la demanda tiene por $t$, es decir, tenemos

$$2^{k^2+t}>(k^2+t)^k$$

También obtenemos $\left(\frac{k^2+t+1}{k^2+t}\right)^k = \left(1+\frac1{k^2+t}\right)^k \le \left(1+\frac1{k^2}\right)^k < 2$.

Multiplicando estos dos inequatities tenemos

$$2^{k^2+t+1}>(k^2+t+1)^k$$

$$2^n>n^k$$

---

El único caso restante es $k=1$, en cuyo caso la reclamación $n\ge 2$ $\Rightarrow$ $2^n>n$ puede demostrarse por inducción.

Answer 2

Si realmente desea utilizar inducción, podría usar este lema que surgió a través de jugando un poco con su desigualdad :)

Lema 1:

$ \left( 1+\frac{1}{n} \right)^k < 2 $ $ k \geq 1 $ (que significa $n \geq 2$)

Prueba de lema 1:

Por la convexidad de $exp$, sabemos que $1+\frac{1}{n} < e^{\frac{1}{n}}$ y así $ \left( 1+\frac{1}{n} \right)^k < e^{\frac{k}{n}} $.

Luego basta para probar que $ \ln 2 - \frac{k}{n} > 0 $, que es inmediata porque $\ln 2 - \frac{k}{n} \geq \ln 2 - \frac{\sqrt{n-1}}{n} = \ln2 - \sqrt{\frac{1}{n} - \frac{1}{n^2}}$ $x \to \frac{1}{x}-\frac{1}{x^2}$ es una función decreciente en $[2,+\infty[$, que $\ln 2 - \sqrt{ \frac{1}{n} - \frac{1}{n^2} } \geq \ln 2 - \frac{1}{2} > 0$, que completa la prueba.

Answer 3

Primero probarlo para $n=k^2 + 1$ y luego usar inducción para demostrar que tiene todo el otro $n$. El caso base sí mismo ahora implica sólo $k$ y tal vez pueda ser probado por inducción en $k$.