¿Cómo puedo demostrar que existe $n_0$ , $c$ tal que para todo $n>n_0$ : $$n^{\log_2{n}}\le c2^{n}$$ (Así que me refiero al logaritmo de n con base 2). ¿Puede alguien ayudarme?
Respuestas
¿Demasiados anuncios?
En primer lugar, vamos a demostrar que $$ \lim_{n\to\infty}\frac{\log(n)^2/\log(2)}{\log(c)+n\log(2)}=0 $$ Si se utiliza L'Hospital dos veces, se obtiene $$ \begin{align} \lim_{n\to\infty}\frac{\log(n)^2/\log(2)}{\log(c)+n\log(2)} &=\lim_{n\to\infty}\frac{2\log(n)/n}{\log(2)^2}\\ &=\lim_{n\to\infty}\frac{2\log(n)}{\log(2)^2n}\\ &=\lim_{n\to\infty}\frac{2/n}{\log(2)^2}\\[6pt] &=0 \end{align} $$ Por lo tanto, hay un $n_0$ de modo que para $n\ge n_0$ $$ \frac{\log(n)^2/\log(2)}{\log(c)+n\log(2)}\le1 $$ Así, $$ \log(n)^2/\log(2)\le\log(c)+n\log(2) $$ y por lo tanto, $$ n^{\log_2(n)}\le c\,2^n $$
portin.daniel
Puntos
671
Sabemos que $\log n \leq \sqrt{n}$ para todos $n > 0$ . Por lo tanto, que $\log n \leq \sqrt{n + \log_2 k}$ para cada $k \geq 1$ y todos $n > 0$ . Si no lo sabes, es fácil demostrarlo utilizando los métodos de cálculo ( $e$ . $g$ ., mira el límite del cociente de $\log n$ y $\sqrt{n}$ o aproximado $\log n$ utilizando un polinomio). Elevando al cuadrado ambos lados de la desigualdad se obtiene $\log^2 n \leq n + \log_2 k$ para todos $n > 0$ . Dividiendo cada lado por $\log 2$ da $\log^2 n / \log 2 \leq n \log 2 + \log k$ para todos $n > 0$ . Por las propiedades fundamentales del logaritmo, obtenemos $\log^2 n / \log 2 \leq \log k2^n$ para todos $n > 0$ . Y como la función exponencial es creciente en su argumento, también que $\exp \log^2 n / \log 2 \leq \exp \log k2^n$ para todos $n > 0$ . Pero $\exp \log k2^n = k2^n$ para que $\exp \log^2 n / \log 2 \leq k2^n$ para todos $n > 0$ . Si observamos que $\log^2 n / \log 2$ es sólo una forma ofuscada de escribir $\log_2 n \log n$ y $\exp{\log^2 n \log n}$ es sólo una forma disfrazada de $n^{\log_2 n}$ obtenemos $n^{\log_2 n} \leq k2^n$ para todos $n > 0$ . Así que para cada real $k \geq 1$ y todos $n > 0$ la desigualdad se mantiene (suponiendo que no hay errores).
