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

Una perspectiva más visual (no estoy seguro de la demostración) es incrustar un árbol formado por $n^{k}$ en el árbol binario formado por $2^{n}$.

Para $k=1$, tenemos la siguiente imagen

(desde "Average Redundancy for Known Sources: Ubiquitous Trees in Source Coding")

A lo largo de cada diagonal en $Z^{2}_{+}$, tenemos un crecimiento lineal 2,3,4,5. Mientras que para el árbol binario tenemos 2,4,8,16. Por lo tanto, la ruta de la rejilla tiene más opciones en el árbol binario.

Vemos que en $Z^{2}_{+}$, cada vértice interior tiene dos padres, por ejemplo (1,1) tiene padres (1,0) y (0,1). Mientras que en el árbol binario, cada padre tiene dos vértices hijos.

Cada camino vertical de la rejilla en $Z^{2}_{+}$ tiene un camino descendente único correspondiente en el árbol binario. Tenemos una biyección. El número de caminos que llegan al nodo $(n,n)$ es exactamente $2n$ (solo necesitamos más de uno). Mientras que en el árbol binario, cada nodo solo puede ser alcanzado por un camino. Por lo tanto, debe haber menos nodos en la diagonal que conecta $(n,0)$ y $(0,n)$, de lo que tenemos en el nivel $n$-ésimo en el árbol binario.

También podríamos preguntarnos "Supongamos que tenemos dos ciudades A y B, en A cada padre puede producir solamente dos hijos y en B cada hijo debe tener dos padres, ¿qué población crecerá más rápido?" es decir, $2^{n}\geq 2n$ para $n\geq 1$.

Para valores más altos de $k$

Creo que para un polinomio $n^k$, podríamos ser capaces de tomar $\mathbb{Z}_{+}^{2k}$ (verificar), porque cada vez que tomamos otro producto cartesiano $\mathbb{Z}_{+}^{2}\times \mathbb{Z}_{+}^{2}\times\dotsb$ proporcionamos otras opciones de $n$. Así que aquí la ruta de la rejilla elige uniformemente el siguiente vértice que está a 1 arista de distancia. No está claro si hay una correspondencia clara con el árbol binario.

Alternativamente, podemos intentar tomar $\mathbb{Z}^{k+1}$ porque básicamente estamos estudiando el número de vértices que están a una distancia de $n$ utilizando la métrica $|x_{1}|+\dotsb+|x_{k}|=n$. Este número crece como $n^{k-1}$ según la teoría de particiones ¿Cuáles son los límites conocidos más altos sobre el número de particiones de $n$ en exactamente $k$ partes distintas?. Pero esto va más allá de lo elemental.

Estoy tratando de pensar si hay una incrustación natural aquí que lo haga obvio, cualquier ayuda será apreciada.

Answer 2

Denota $L=\lim_{n\rightarrow\infty}n^k/2^n$ y considera que $$L=\lim_{n\rightarrow\infty}\frac{(n+1)^k}{2^{n+1}}=\tfrac{1}{2}L\lim_{n\rightarrow\infty}(1+1/n)^k=\tfrac{1}{2}L\Rightarrow L=0.$$

Puedes encontrar más "demostraciones" en https://math.stackexchange.com/q/55468/87355

---

actualización en respuesta a los comentarios: ¿puede $L$ ser infinito?

si $L_n\equiv n^k/2^n$, entonces, $L_{n+1}=\tfrac{1}{2}(1+1/n)^k L_n para $n\geq N$ suficientemente grande;
así, $L_n=L_{N}\frac{L_{N+1}}{L_{N}}\frac{L_{N+2}}{L_{N+1}}\cdots \frac{L_{n}}{L_{n-1}} para $n>N$.

Answer 3

Aquí hay una demostración sin límites, sin logaritmos y sin "suficientemente grande".

Sea $n=4^k$. Estamos tratando de probar que

$$ 2^{4^k} > (4^k)^k.$$

Usando las propiedades de la exponencial (que se pueden demostrar con un argumento combinatorio elemental), esto es equivalente a probar que

$$ 2^{4^k} > 2^{2k^2}.$$

Luego, note que $2^x$ es monótonamente creciente, por lo que esto es equivalente a probar que

$$4^k > 2k^2.$$

Esto, lo probaremos mediante inducción. Como caso base, para $k=1$, tenemos que $4>2$.

Inductivamente, asumamos que la afirmación se cumple para $k$. Note que $4\ge ((k+1)/k)^2$ para todo $k\ge 1$. Multiplicando las dos desigualdades, obtenemos

$$ 4^k \cdot 4 > 2k^2 ((k+1)/k)^2$$ $$4^{k+1} \ge 2(k+1)^2.$$

Eso prueba la inducción y completa la demostración.

---

Esta demostración podría ser hecha completamente combinatoria al reemplazar cada desigualdad con un mapeo inyectivo entre cadenas en algunos alfabetos, y construyendo a partir del mapeo de $4^k > 2k^2$ al mapeo de $2^{4^k} > (4^k)^k$.

En particular, aquí hay un mapeo explícito de $2^{2k-1} > k^2$:

Queremos mapear de manera única desde cadenas de longitud 2, donde los caracteres son $k$-arios, a cadenas binarias de longitud $2k-1$.

Sea la cadena de longitud 2 $xy$. Coloque un 1 en la posición $x$ y en la posición $k+y$. Llene todas las demás posiciones con $0$. Si $y=k$, simplemente omita el segundo 1 - aún podemos deducirlo.

Answer 4

Aquí está una demostración completamente elemental, sin propiedades de logaritmos, expansiones binomiales o límites. ¡Por otro lado, ciertamente no es una demostración "del libro"! Volviendo a la primera mano, podemos comparar cualquier exponencial creciente, no solo $2^n$.

Paso 1: Desigualdad de Bernoulli: Para todo $x>-1$ y todos los enteros $n \geq0$, $(1+x)^n \geq 1 + nx$. Esto se puede demostrar por inducción muy elemental.

Paso 2: Ahora, las exponenciales superan a las lineales: dado una función exponencial $(1+x)^n$ con $x > 0$ (nota: aquí $x$ es constante, y consideramos esto como una función de $n$) y dado una pendiente $m$, tenemos $(1+x)^n > m/x$ para $n$ mayor que algún $n_0$, y luego $(1 + x)^n > (m/x)( 1 + (n-n_0)x)$, que es una función lineal de $n$ de pendiente $m$. Hemos renunciado al control del término constante, pero podemos recuperarlo: la exponencial eventualmente supera alguna función lineal de pendiente $m+1$, que a su vez eventualmente supera cualquier función lineal de pendiente $m$.

Paso 3: Ahora fijemos $k$. Tenemos en particular $(1 + x)^n > k(n+1)$ para $n$ mayor que algún $n_1$. Para $n \geq k n_1$, sea $q$ tal que $qk \leq n < (q+1)k$. Tenemos:

$$ (1+x)^n \geq ((1+x)^q)^k > (k(q+1))^k > n^k $$

Aquí tenemos: $a^n > n^k$ para todo $a>1$, $k \geq 0$, y enteros suficientemente grandes $n$, lo cual creo que ya va un poco más allá que la pregunta original ($2^n > n^k$). En caso de que alguien esté interesado en "qué tan elemental puede ser la demostración de que $a^x$ eventualmente supera a cualquier polinomio" (es decir, extendiéndose a cualquier polinomio, y a números reales), aquí está.

Paso 4: Dado $a > 1$ y un polinomio $f$, sea $k$ el grado de $f$, $t$ el número de términos, y $M$ una cota para sus coeficientes, de modo que cada coeficiente de $f$ esté entre $M$ y $-M$. Para $n$ suficientemente grande, $a^n > n^{k+1} > Mtn^k \geq |f(n)|$.

Siguiente: números reales.

Paso 5: En particular $a^n > (n+1)^k$ eventualmente. Para $x$ suficientemente grande tenemos

$$a^{x} \geq a^{\lfloor x \rfloor} > (\lceil x \rceil)^k \geq x^k $$

Finalmente repetimos la maniobra en el paso 4 para obtener $a^x > f(x)$ para todo $a>1$, polinomios $f$, y $x$ suficientemente grande.

Otra vez, esta respuesta solo se ha centrado en la parte "completamente elemental" de la pregunta original y de ninguna manera pretende ser "del libro". Tampoco hago ninguna sugerencia sobre el uso de esta presentación en la instrucción.

Answer 5

Yo seré mucho más concreto que otros que responden:

Suponga que incrementa $x$ desde $1\text{ zillion}$ hasta $(1\text{ zillion}) + 1.$ Entonces $2^x$ se vuelve el doble de grande, mientras que $x^n$ crece una cantidad que, aunque enorme, es microscópica en comparación con el inmenso tamaño de $(\text{1 zillion})^n.$

Intentaría asegurarme de que el estudiante comprenda que esa es la idea central antes de abordar la pregunta de cómo sabemos que eso es cierto.

Incluso estudiantes que obtienen calificaciones de $\text{“A}{+}\text{”$}$ en álgebra y son magníficamente hábiles en todas las técnicas de álgebra que se les pide dominar generalmente no entienden nada a través del álgebra. Por ejemplo, supongamos que tal estudiante afirma saber que $1+\prod_{p\in S} p$ no es divisible por ninguno de los miembros de $S,$ y demuestran que conocen todos los pasos en una prueba de ese hecho, y entienden que demostrar ese hecho es el propósito de esos pasos. Luego dices que $1+(2\times3\times7) =43$ no puede ser divisible por $7$ ya que el siguiente número después de $42$ que es divisible por $7$ es $42+7$ y el último antes de eso que es divisible por $7$ es $42-7,$ y por la misma razón, $1+(2\times3\times7)$ no puede ser divisible por $2$ o por $3,$ y dicen que nunca habían entendido eso antes. He visto esto pasar cientos de veces (aunque solo unas pocas veces con una prueba de esta proposición en particular). El hecho de que el objetivo del álgebra fuera llevarlos al punto de entender eso que luego entendieron solo a través de ejemplos concretos como este simplemente no está presente en sus mentes en absoluto.