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

Para $n>k+1$, sustituye $2n$ en lugar de $n$ tanto en $2^n$ como en $n^k$. Ten en cuenta que el primero se multiplica por $2^n$ y el segundo por $2^k$, que es al menos dos veces más pequeño. Por lo tanto, aplicando esto lo suficiente veces hará que $2^n$ sea más grande que $n^k$, ya que ambos son mayores que $0$.

Answer 2

Suponga que $n>k$. Entonces $$2^n=\sum_{j=0}^n {n\choose j}>{n\choose k+1}=n^k\left(\frac{n}{(k+1)!}+O(1)\right).$$

Answer 3

La forma más limpia que se me ocurre es demostrar que si $p(n)$ es cualquier polinomio con coeficientes enteros, entonces eventualmente $p(n)<2^n$ para $n$ suficientemente grande.

Prueba

La prueba es por inducción, siendo el caso de grado cero obviamente verdadero.

Supongamos que el resultado vale para grados menores que $k$, y que $p(n)$ tiene grado $k$.

Entonces $p(n+1)-p(n)$ tiene grado estrictamente menor que $k$ (ni siquiera es necesario recurrir a la expansión binomial completa para convencer a un estudiante de esto, solo observar que $(n+1)^k=n^k+\dots$, donde los términos restantes tienen grado menor que $k$).

Por lo tanto, eventualmente

$$p(n+1)-p(n)<2^n = 2^{n+1}-2^n,$$ o equivalentemente, $$2^n-p(n) < 2^{n+1}- p(n+1).$$

Así que $2^n-p(n)$ es eventualmente estrictamente creciente, y por lo tanto (como una secuencia de números enteros) eventualmente se volverá positiva y permanecerá así, por lo que se demuestra el caso para grado $k$.

Answer 4

Creo que esta es una explicación buena para una variedad de niveles. Esto está en algunas de las otras respuestas, pero enfatizaría que escribirlo con discusión en cada punto puede ser más claro que parte de la computación.

Considera la proporción entre términos consecutivos en $n^k$: $\left(\frac{n+1}{n}\right)^k$.

Y compara $$n^k = \left(\frac{2}{1}\right)^k \left(\frac{3}{2}\right)^k \cdots \left(\frac{n}{n-1}\right)^k$$ $$2^n = \underbrace{2 \cdot 2 \cdots 2}_{\text{n veces}}$$

Creo que aquí algunos estudiantes ya pueden imaginar el resto de la explicación.

Ahora, necesitas explicar que podemos encontrar $n_0$ tal que $\left(\frac{n}{n-1}\right)^k < 1.5$. (Por supuesto, más fácil tomando logaritmos :) pero creo que esto es más intuitivo que el hecho original.)

Y luego necesitas explicar que podemos escribir

$$n^k = \left(\frac{2}{1}\right)^k \left(\frac{3}{2}\right)^k \cdots \left(\frac{n_0}{n_0-1}\right)^k \left(\frac{n_0+1}{n_0}\right)^k \cdots \left(\frac{n}{n-1}\right)^k$$ $$n^k \leq \underbrace{\left(\frac{2}{1}\right)^k \left(\frac{3}{2}\right)^k \cdots \left(\frac{n_0}{n_0-1}\right)^k}_{\text{alguna constante}} \underbrace{\frac{3}{2} \cdots \frac32}_{n-n_0 \text{ veces}}$$

Y se reduce a explicar que, si $a > b$, entonces $C_1 a^n$ eventualmente supera a $C_2 b^n$.

En un pizarrón o con algunas imágenes, puedes sacar mucho escribiendo los resultados en la forma "$\cdots$", ya que puedes poner un cuadrado grande alrededor de los términos que metemos en la "constante" y enfatizar que no nos importa cuán grande llegamos hasta ese punto. Me gusta esta explicación porque creo que es bastante abierta a la discusión a medida que avanzas e invita a pensar a los estudiantes avanzados; por ejemplo, ¿cómo afecta la elección de $3/2$ cosas como las estimaciones finales que obtenemos? ¡Finalmente estamos acotando el crecimiento polinómico desde arriba por crecimiento exponencial!

Answer 5

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.