Cuál es asintóticamente mayor: $n 2^n$ o $3^n$ ?

Question

Cuál de las siguientes funciones es mayor asintóticamente: $n 2^n$ o $3^n$ ?

Si tomo $\log$ en ambas funciones y luego comparar, estoy recibiendo $n 2^n$ como más grande, pero la respuesta dada es $3^n$ . ¿En qué me estoy equivocando?

$n 2^n$ contra. $3^n$ equivale a comparar $\log(n 2^n)$ contra. $\log 3^n$ o $\log_2 n +n$ contra. $n \log_2 3$ ¿Cómo debo proceder ahora?

Answer 1

Considere $\displaystyle f(x)=\sum_{n=0}^{\infty} x^n=\frac{1}{1-x}$ para $|x|<1$ . Entonces $\displaystyle xf'(x)=\sum_{n=0}^{\infty} nx^n$ .

Tomando $x=\dfrac{2}{3}$ vemos que la serie para $xf'(x)$ converge y así $$\lim_{n\to\infty}\dfrac{n 2^n}{3^n}=0$$

Esto significa que $3^n$ es asintóticamente mayor que $n2^n$ .

Al considerar las derivadas superiores, vemos que $3^n$ es asintóticamente mayor que $n^k2^n$ y por tanto es asintóticamente mayor que $p(n)2^n$ para cada polinomio $p$ .

Answer 2

Consideremos $\dfrac {3^n} {n 2^n}$ :

$$\frac {3^n} {n 2^n} = {\rm e} ^{\log \frac {3^n} {n 2^n}} = {\rm e} ^{\log 3^n - \log (n 2^n)} .$$

Ahora

$$\log (3^n) - \log (n 2^n) = n \log 3 - \log n - n \log 2 = n \left( \log 3 - \log 2 - \frac {\log n} n \right)$$

y

$$\lim \limits _{n \to \infty} \frac {\log n} n = 0, \quad \log 3 - \log 2 > 0 ,$$

así que

$$\lim \limits _{n\to \infty} \frac {3^n} {n 2^n} = \infty .$$

Answer 3

Sobre la expansión del binomio,

$3^n = (2+1)^n = {{n} \choose {0}} \cdot 2^n + {{n} \choose {1}} \cdot 2^{n-1} + \cdot \cdot \cdot$

Así que,

$3^n > n \cdot 2^{n-1} \approx n \cdot 2^n \cdot \frac{1}{2} \approx n \cdot 2^n$

Porque las constantes no importan en las comparaciones asintóticas.

Así que,

$$3^n > n \cdot 2^n$$