La prueba más elemental que demuestra que el crecimiento exponencial gana contra el crecimiento polinomial

Question

Esta pregunta está motivada por la enseñanza: Me gustaría ver una demostración completamente elemental que muestre, por ejemplo, que para todos los números naturales $k$ eventualmente tenemos $2^n>n^k$.

Todas las demostraciones que conozco de alguna manera se basan en propiedades del logaritmo. (No tengo nada en contra de los logaritmos, pero a algunos estudiantes les desagradan).

¿Existe una "demostración del libro" brillante para esta desigualdad (por ejemplo, dada por una inyección explícita y sencilla de un conjunto conteniendo $n^k$ elementos en, digamos, el conjunto de subconjuntos de $\lbrace 1,\ldots,n\rbrace$ para $n$ suficientemente grande)?

Una demostración bastante fácil pero algo computacional (que me deja insatisfecho):

Dado $k$ elige $n_0>2^{k+1}$. Para $n>n_0$ tenemos \begin{align*} &\frac{(n+1)^k}{2^{n+1}}\\ &=\frac{1}{2}\left(\frac{n^k}{2^n}+\frac{\sum_{j=0}^{k-1}{k\choose j}n^j}{2^n}\right)\\ &\leq \frac{n^k}{2^n}\left(\frac{1}{2}+\frac{2^k}{2n_0}\right)\\ \leq \frac{3}{4}\frac{n^k}{2^n} \end{align*} mostrando que la razón $\frac{n^k}{2^n}$ decae exponencialmente rápido para $n>n_0$.

Una prueba quizás más elemental pero un poco descuidada es la observación de que los dígitos de $n\longmapsto 2^{2^n}$ (aproximadamente) se duplican al aumentar $n$ en $1$ mientras que los dígitos de $n\longmapsto (2^n)^k$ forman (aproximadamente) una progresión aritmética. (Y esta "demostración" usa por lo tanto propiedades del logaritmo de manera encubierta).

Adición: La prueba de Fedor Petrov se puede reescribir ligeramente como $$2^{n+k}=\sum_j{n+k\choose j}>{n+k\choose k+1}>n^k\frac{n}{(k+1)!}$$ mostrando $$2^n>n^k\frac{n}{2^k(k+1)!}>n^k$$ para $n>2^k(k+1)!$.

Segunda adición: Aquí hay una especie de prueba "injetiva": $n^{k+1}$ es el número de secuencias $(a_1,a_2,\ldots,a_{k+1})\in \lbrace 1,2,\ldots,n\rbrace^{k+1}$. Escribiendo las correspondientes expresiones binarias, añadiendo ceros principales para hacerlas de igual longitud $l\leq n$ (con $l$ tal que $n<2^l$) y concatenándolas obtenemos una representación binaria de un entero $<2^{l(k+1)}\leq 2^{n(k+1)}$ que codifica de manera única $(a_1,\ldots,a_{k+1}). Esto muestra $$2^{(k+1)n}>n^{k+1}.$$ Reemplazando $(k+1)n$ por $N$ obtenemos $$2^N>N^k\frac{N}{(k+1)^{k+1}}>N^k$$ para $N$ en $(k+1)\mathbb N$ tal que $N>(k+1)^{k+1}$.

Para el caso general tenemos $$2^{N-a}>N^k\frac{N}{2^a(k+1)^{k+1}}>(N-a)^k\frac{N-a}{2^a(k+1)^{k+1}}>(N-a)^k$$ (donde $a$ está en $\lbrace 0,1,\ldots,k\rbrace$) si $N-a>2^k(k+1)^{k+1}$.

Variación para la última prueba: Se pueden reemplazar las representaciones binarias por funciones características: $a_i$ está codificado por el vector de base $a_i$-ésima de $\mathbb R^n$. Concatenando los coeficientes de estos $k+1$ vectores de base obtenemos un subconjunto (consistente en $k+1$ elementos) de $\lbrace 1,\ldots,(k+1)n\rbrace$.

Answer 1

Por el teorema del binomio $$ 2^{\frac{n}{k}} =(1+\sqrt[k]{2}-1)^n > \binom{n}{2}(\sqrt[k]{2}-1) $$ Ahora, para $n$ suficientemente grande (esto se puede calcular explícitamente) tenemos $$ \binom{n}{2}(\sqrt[k]{2}-1) >n $$

Answer 2

Para algún entero positivo fijo $k$, sea $n^k < 2^n < n^{k+1}$

Ahora, si pasamos de $n$ a $n+1$ y tomamos ratios obtenemos: $\frac{2^{n+1}}{2^n} = 2 > \frac{(n+1)^{k+1}}{n^{k+1}}= \left(1 + \frac{1}{n}\right)^{k+1} = 1$ para $n$ grande y $k$ fijo.

Answer 3

Yo sugeriría considerar en su lugar la afirmación más fuerte de que $n^k/2^n \to 0$. (Esto, por supuesto, requeriría una explicación de lo que significa que una función converge a cero a medida que el argumento tiende a infinito). Dado que $n^k/2^n \to 0$ implica $n^{2k}/2^n \to 0$ al elevar al cuadrado, podemos reducirlo a $k=1$.

Por lo tanto, tenemos que demostrar que $n/2^n \to 0$. Podemos representar esto visualmente comparando $n=\underbrace{1+1+\ldots+1}_{\textrm{$n$ sumandos}}$ con $2^n=\underbrace{2 \times 2 \times \ldots \times 2}_{\textrm{$n$ factores}}$. Ahora, la primera expresión siempre es menor que la segunda, e intuitivamente es completamente obvio que la relación entre los dos puede aumentarse indefinidamente, ya que se hace que un número aumente más rápido al multiplicar repetidamente por $2$ que al sumar repetidamente $1$. Este debería ser un argumento convincente para cualquiera que haya jugado con una calculadora.

De hecho, creo que lo dejaría así. No es una "prueba", por supuesto, pero aun así, convencería a la mayoría de las personas de que la afirmación debe ser cierta (y por lo tanto que debe existir una prueba).

Por supuesto, terminar la prueba tampoco es difícil, ya que $\frac{n+1}{n}$ disminuye monótonamente (y es igual a $3/2$ en $n=2$) mientras que $\frac{2^{n+1}}{2^n}=2$.

De hecho, dado que $\frac{n+1}{n} \to 1$, este argumento demuestra que la relación entre las dos expresiones es $> C_{\epsilon} 2^{n(1-\epsilon)}$ para cualquier $\epsilon>0$, lo que implica $n < C_{\epsilon}^{-1} 2^{\epsilon n}$. A partir de esto, fácilmente se obtiene la afirmación para $k$ general.

Answer 4

Primero se establece el caso más simple $2^{m} > m^{2}$ para $m > 4$, por ejemplo, por inducción: la desigualdad se cumple para $m = 5$ y $2^{m+1} = 2 \cdot 2^m > 2 m^2 = m^2 + m^2 > m^2 + 2m + 1 = (m+1)^2$, ya que $m^2 > 3m > 2m+1$ para $m \geq 5$.

Luego, dado $k > 1$, se muestra que existen $n$ arbitrariamente grandes para los cuales $2^n > n^k$. Basta tomar $n := 2^{ak}$ para $ak > 5$, ya que $2^{n} = 2^{(2^{ak})} > 2^{((ak)^2)} = n^{ak} > n^k$.

Finalmente, si $n$ es suficientemente grande, entonces $(n+1)^{k} / n^{k} = (1+\frac{1}{n})^{k} < 2$, mientras que $2^{n+1} / 2^{n} = 2$, por lo que $2^n > n^k$ implica $2^{n+1} > (n+1)^k$. Por lo tanto, la desigualdad requerida se cumple para todos los $n$ lo suficientemente grandes.

Answer 5

$n \ge k^2 \implies n \ge k \sqrt{n} \implies 2^{n} \ge 2^{k \sqrt{n}}$. Y $\sqrt{n} \ge \log_2(n)$ para $n$ suficientemente grande, entonces $2^{k \sqrt{n}} \ge 2^{k \log_2(n)} = n^k$.