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$.
