n! v.s. $a^{n}$ ¿Cómo podemos saber cuál es más rápido sin hacer un gráfico?

Question

N! v.s. $a^{n}$ Si nos dan un número arbitrario a (a>1). ¿Cómo podemos saber cuál es más rápido como n->INFINITO sin graficar?

Answer 1

Para $n \rightarrow \infty$ , $n!$ siempre va a ganar. Tenemos

\begin{align*} \frac{a^n}{n!} & = \frac{a}{1} \frac{a}{2} \ldots \frac{a}{n-1} \frac{a}{n} \end{align*}

Ahora, dejemos que $N$ sea el menor número entero que satisfaga $N \geq a$ . Además $n > N$ . Tenemos

\begin{align*} \frac{a^n}{n!} & = \underbrace{\frac{a}{1} \frac{a}{2} \ldots \frac{a}{N-1}}_{>1} \times\underbrace{\frac{a}{N} \frac{a}{N+1} \ldots \frac{a}{n-1} \frac{a}{n}}_{<1} \end{align*}

donde la cola se hace cada vez más pequeña al aumentar $n$ . Ahora puede comprobar que la cola de este producto "abruma" a la cabeza por $n$ suficientemente grande.

Answer 2

Por favor, echa un vistazo a la aproximación de Sterling http://en.wikipedia.org/wiki/Stirling%27s_approximation

Answer 3

Del $n$ factores en $n!$ la mitad son mayores que $\frac n2$ Así que $ n! \ge (\tfrac n2)^{n/2} = \left(\sqrt{\tfrac n2}\right)^n >\!\!> a^n $ porque $\sqrt n >\!\!> a$ .