La forma más sencilla de probar $2^n \geq A n^k$ ?

Question

¿Cuál es la forma más sencilla y menos exigente de demostrar que las exponenciales crecen más rápido que las potencias? Hasta ahora he encontrado una prueba que se basa en La desigualdad de Berloulli (*) que es elegante pero no parece intuitivo ni sencillo. ¿Podemos hacerlo mejor?

Por supuesto, podrías utilizar los teoremas de de L'Hopital o de Taylor, pero requerirían que introdujeras derivadas, por lo que no podrías utilizarlos cuando estás introduciendo estos límites por primera vez, mientras que todavía necesitas afirmar que las exponenciales crecen más rápido.

(*) Aquí está: $$ 2^n=[(\sqrt{2})^n]^2=[(1+(\sqrt{2}-1))^n]^2\geq\\ [1+n(\sqrt{2}-1)]^2\geq n^2(\sqrt{2}-1)^2 $$ y también $$ 2^n=[(\sqrt[3]{2})^n]^3=[(1+(\sqrt[3]{2}-1))^n]^3\geq\\ [1+n(\sqrt[3]{2}-1)]^3\geq n^3(\sqrt[3]{2}-1)^3 $$ y así sucesivamente...

Answer 1

Creo que una forma fácil de pensar en ello (y en muchos otros problemas más difíciles relativos al análisis asintótico) es considerar tasa de crecimiento . La secuencia exponencial $\{2^{n}\}_{n=1}^{\infty}$ tiene una tasa de crecimiento constante de 2, mientras que la secuencia polinómica $n^{k}$ tiene una tasa de crecimiento de $\{(1+\frac{1}{n})^{k}\}$ que eventualmente cae por debajo de, digamos, 1,5. Por lo tanto, a partir de algún punto, la relación de $2^{n}$ a $n^{k}$ crecerá al menos al ritmo de $2/1.5$ . Así, el cociente superará a cualquier número real dado.

Edición: Parece que tengo que explicar por qué basta con demostrar la relación asintótica $n^{k}=o(2^{n})$ y aquí está: nótese que cualquier secuencia de números positivos que es eventualmente creciente tiene un límite inferior, por lo que debe existir un $A$ tal que $2^{n}/n^{k}>A$ para todos $n\in\mathbb{N}$ .

Edición: Si realmente quieres una forma cerrada elegante para $A$ entonces supongo que su construcción por la desigualdad de Bernoulli es muy probablemente la más fácil. También hay que tener en cuenta que calculando la $n$ en la que la tasa de crecimiento de $\{n^{k}\}_{n=1}^{\infty}$ cae de $>2$ a $<2$ se puede obtener el valor óptimo de $A$ .

Answer 2

Inspirado en el comentario de dxiv en el OP, podemos simplemente notar que para $n\ge2k$ , $$ 2^n = (1+1)^n = \sum_{j=0}^n \binom nj \ge \binom nk = \frac{n(n-1)\cdots(n-k+1)}{k!} \ge \frac{(n/2)(n/2)\cdots(n/2)}{k!} = \frac1{2^kk!} n^k. $$