¿Cómo probar que lo exponencial crece más rápido que lo polinómico?

Question

En otras palabras, cómo probar:

Para todas las constantes reales $a$ y $b$ de tal manera que $a > 1$ ,

$$\lim_ {n \rightarrow\infty } \frac {n^b}{a^n} = 0$$

Conozco la definición de límite pero creo que no es suficiente para probar este teorema.

Answer 1

Podemos limitar la atención a $b \ge 1$ . Esto se debe a que, si $0<b<1$ entonces $n^b \le n$ . Si podemos demostrar que $n/a^n$ se acerca a $0$ se deduce que $n^b/a^n$ se acerca a $0$ para cualquier $b\le 1$ . Así que a partir de ahora tomamos $b \ge 1$ .

Ahora mira $n^b/a^n$ y tomar el $b$ -en la raíz. Obtenemos $$\frac{n}{(a^{1/b})^n}$$ o de forma equivalente $$\frac{n}{c^n}$$ donde $c=a^{1/b}$ .

Tenga en cuenta que $c>1$ . Si podemos demostrar que $n/c^n$ se acerca a $0$ como $n\to\infty$ estaremos acabados.

Pues nuestra secuencia original está formada por el $b$ -enésima potencia de la nueva secuencia $(n/c^n)$ . Si podemos demostrar que $n/c^n$ tiene límite $0$ y después de un tiempo, $n/c^n \le 1$ y así, después de un tiempo la antigua secuencia es, término por término, $\le$ la nueva secuencia. (Recordemos que $b\ge 1$ .)

El progreso, sólo tenemos que mirar $n/c^n$ .

¿Cómo seguimos? De cualquiera de las formas sugeridas en los otros posts. O bien, dejemos que $c=1+d$ . Tenga en cuenta que $d$ es positivo. Obsérvese también que a partir del Teorema del Binomio, si $n \ge 2$ tenemos $$c^n=(1+d)^n \ge 1+dn+d^2n(n-1)/2\gt d^2(n)(n-1)/2.$$

De ello se desprende que $$\frac{n}{c^n}< \frac{n}{d^2(n)(n-1)/2}=\frac{2}{d^2(n-1)}.$$ y está claro que $\dfrac{2}{d^2(n-1)} \to 0$ como $n\to\infty$ .

Answer 2

Podríamos demostrarlo por inducción a los enteros $k$ :

$$\lim_{n \to \infty} \frac{n^k}{a^n} = 0.$$

El caso $k = 0$ es sencillo. Le dejaré el paso de la inducción a usted. Para ver cómo esto implica la afirmación para todos los reales $b$ Sólo hay que tener en cuenta que todo número real es menor que algún entero. En particular, $b \leq \lceil b \rceil$ . Así,

$$0 \leq \lim_{n \to \infty} \frac{n^b}{a^n} \leq \lim_{n \to \infty} \frac{n^{\lceil b \rceil}}{a^n} = 0.$$

La primera desigualdad se deduce porque todos los términos son positivos. La última igualdad se desprende de la inducción que establecimos anteriormente.

Answer 3

En primer lugar, observe que $(n+1)^b/n^b=1$ más los términos en potencias negativas de $n$ , por lo que pasa a 1 como $n\to\infty$ (con $b$ arreglado). Ahora, al pasar de $n^b/a^n$ a $(n+1)^b/a^{n+1}$ Si el numerador se multiplica por algo que va a ser 1, pero el denominador por algo que no lo es (es decir, por $a\gt1$ ).

Answer 4

Considerar la función exponencial como la única solución al problema de valor inicial $f(0) = 1$ con $f' = f$ . La formulación integral equivalente es

$f(t) = 1 + \int_0^t f(s) ds$

Primero demuestre que $f$ es una función creciente. Para $t \geq 0$ se puede utilizar un argumento de método de continuidad considerando el conjunto $\{ s ~:~ f \mbox{ increases on } [0, s] \}$ . El supremum de este conjunto no puede ser finito. Para $s < 0$ también se puede considerar la EDO satisfecha por $f^2$ pero eso no te preocupa. Ahora que sabemos $f$ aumento, también sabemos $f$ crece al menos linealmente:

$f(t) \geq 1 + \int_0^t 1 ds = (1 + t)$

También crece al menos cuadráticamente..

$f(t) \geq f(\frac{t}{2}) + \int_{t/2}^t f(s) ds \geq (1 + t/2) f(t/2)$

Y repitiendo se obtiene

$f(t) \geq (1 + t/2)^2$

En general, $f(t) \geq (1 + t/n)^n$ por el mismo método. Incluso es cierto para $n$ no un número entero. En este caso, la función $(1 + t/n)^n$ se define en primer lugar como $e^{n \log( 1 + t/n) }$ . Entonces, como log x está definido por la integral $\int_1^x \frac{1}{t} dt = x \int_0^1 (1 + sx)^{-1} ds$ podemos reescribir

$(1 + t/n)^n = e^{n \log (1 + t/n) } = \mbox{exp}(t \int_0^1 (1 + \frac{s t}{n})^{-1} ds ) \leq e^t$

EDIT: Esta respuesta puede no ser tan útil para usted. No he leído el final de tu pregunta, así que puede que no sepas cómo trabajar con la mayoría de las cosas que he escrito. La razón principal por qué el exponencial crece más rápido que un polinomio es porque si $f$ es exponencial, entonces $f(n+1)$ es por lo menos una vez constante $f(n)$ mientras que cuando $f$ es un polinomio, $f(n+1)$ es aproximadamente del mismo tamaño que $f(n)$ cuando $n$ es grande. Al fin y al cabo, apenas se nota la diferencia entre el volumen de un cubo enorme, y un cubo enorme 1 unidad más largo en cada dirección.

Answer 5

Intenta expresar ambos en términos de la exponencial $e^x$ : $n^b$ = $e^{bln(n)}$ ; $a^n=e^{nln(a)}$ para que el cociente se convierta en..:

$\frac{n^b}{a^n}$ = $\frac{e^{bln(n)}}{e^{nln(a)}}=e^{bln(n)-nln(a)}=e^{bln(n)-kn}=\frac{e^{nlna}}{e^{kn}}$ donde k es una constante real. ¿Puedes decir cuál de ln(n) o n crece más rápido?