Demostrar que $n^k < 2^n$ % todo grande $n$

Question

Si $k\ge 2$ es un entero, probar por medios elementales (ningún cálculo o límites) que hay un $N(k)$ tal que $n^k < 2^n$ % enteros todos $n \ge N(k)$. Dar una forma explícita para $N(k)$.

Answer 1

Tenga en cuenta que un polinomio con positivo líder coeficiente finalmente es positivo: Si $$p(x)=a_0+\dots+a_nx^n$$ and $a_n>0$, then $p(x)>0$ for $x$ large enough. For example, we can write $p(x)=a_n[(c_0+\dots+c_{n-1}x^{n-1})+x^n]$, y se nota que $$ |c_0+\dots+c_{n-1}x^{n-1}|\le |c_0|+\dots+|c_{n-1}|x^{n-1}\le x^n/2 $$ mientras $K:=\max\{1,2n|c_i|\colon i<n\}<x$, lo $\displaystyle |c_i|<\frac{x}{2n}$ todos los $i$, e $x^k<x^n$ todos los $k<n$. Esto significa que $$ |p(x)|\ge a_n(x^n-|c_0+\dots+c_{n-1}x^{n-1}|)\ge a_n(x^n-x^n/2)>0, $$ la desigualdad de la celebración de, al menos, para $x>K$.

Ahora, para$n>0$, $\displaystyle 2^n\ge\binom n{k+1}$ (desde el lado izquierdo cuenta con todos los subconjuntos de un conjunto de $n$ elementos, y el lado derecho sólo cuenta los subconjuntos de tamaño exactamente $k+1$), y el último es un polinomio de grado $k+1$ y positiva coeficiente inicial. Esto significa que (por el párrafo anterior) que $\displaystyle \binom n{k+1}>n^k$ $n$ lo suficientemente grande, como $\displaystyle \binom n{k+1}-n^k$ es un polinomio con positivo coeficiente inicial. Pero, a continuación,$2^n>n^k$, como queríamos.

El valor de $K$ puede ser calculada directamente a partir de la expansión de la $\displaystyle \binom n{k+1}-n^k$.

Answer 2

Escribir la desigualdad como $n < 2^{n/k}$.

Supongamos que esto es cierto para $n$. Quiero encontrar condiciones tales que esto también es cierto para $n+1$.

Por supuesto, $n+1 = n(1+\frac1{n}) < 2^{n/k}(1+\frac1{n}) $ y esto es menos de $2^{(n+1)/k}$ si $2^{n/k}(1+\frac1{n}) < 2^{(n+1)/k}$ o $2^{1/k} > 1+\frac1{n}$.

He mostrado en otra solución (de $(1+\frac{x}{k})^k < \frac1{1-x}$ para$0 < x < 1$,$x = \frac12$) que $2^{1/k} > 1+\frac1{2k}$, por lo tanto, si $n \ge 2k$ y $2^n > n^k$, entonces $2^m > m^k$ todos los $m \ge n$.

Ahora tenemos que encontrar una inicial $n \ge 2k$ tal que $2^n > n^k$.

Vamos a tratar de $n = ak$ algunos $a$. $2^{ak} > (ak)^k \iff 2^a > ak $. Casi, pero no del todo.

Vamos a tratar de $n = k^2$. $2^{k^2} > (k^2)^k \iff 2^{k} > k^2 $. Esto es fácil por inducción. $2^5 > 5^2$, y, si $2^k > k^2$$k \ge 5$, $$(k+1)^2 = k^2+2k+1 = k^2(1+\frac{2}{k}+\frac1{k^2}) < 2^k(1+\frac{2}{5}+\frac1{25}) < 2^k(2) = 2^{k+1} $$

Así, por esta anidada de inducción, si $k \ge 5$, si $n \ge k^2$ (de modo que, ciertamente, $n \ge 2k$), $2^n > n^k$.

Para$k = 2, 3,$$4$, valores respectivos de $n \ge 2k$ tal que $2^n > n^k$ $5$ ($2^5 > 5^2$), $10$ ($2^{10} > 10^3$), y $17$ ($2^{17} = 131072> 17^4=83521$).

Estos valores de $n$ pasan a ser $k^2+1$, así que el resultado final es:

Si $n$ $k$ son enteros y $k \ge 2$ y $n \ge k^2+1$, entonces $2^n > n^k$.

Answer 3

Por Bernoulli

$$\sqrt[2k]{2}^n \geq 1+n(\sqrt[2k]{2}-1) \,.$$

Elegir un $N(K)$ para que

$$\sqrt{N(K)}(\sqrt[2k]{2}-1) > 1 \,.(*)$$

Entonces, para todos los $n > N(K)$ tenemos

$$\sqrt[2k]{2}^n \geq 1+n(\sqrt[2k]{2}-1) > \sqrt{n}\sqrt{N(K)}(\sqrt[2k]{2}-1) > \sqrt{n} \,.$$

El valor que obtenemos para $N(K)$ $(*)$ es:

$$N(K)=1+\left\lfloor \left( \frac{1}{\sqrt[2k]{2}-1} \right)^2 \right\rfloor $$

Answer 4

Elegir $n > 2k$. Entonces, $$ 2 ^ n > \binom{n}{k + 1} = \frac{n (n - 1) \cdot \ldots \cdot (n - k)}{(k+1)!} \geq \frac{n^{k + 1}} {2 ^ {k+1} (k + 1)!} $$ por una discusión combinatoria trivial de la primera desigualdad y el uso de $n - k > n/2$ en la segunda desigualdad. Por lo tanto $2^n > n^k$ en cuanto $$ n > 2 ^ {k+1} (k + 1)! $$