Una combinatoria de la prueba de $n^n(n+2)^{n+1}>(n+1)^{2n+1}$?

Question

La declaración es simplemente que la secuencia de $\left(1+\frac{1}{n}\right)^n$ es cada vez mayor.

Dado que los números $n^m$ tiene bastante natural combinatoria interpretaciones, me hace preguntarme si de una combinatoria prueba existe, pero no he sido capaz de encontrar uno.

Por ejemplo, si dejamos a $S_{n,m}$ denota el conjunto de la función $\{1, \dots, n\} \\{1, \dots, m\}$, entonces una prueba iba a seguir a partir de la construcción de una inyección de$S_{2n+1,n+1} \hookrightarrow S_{n, n} \times S_{n+1,n+2} $, o de un surjection va para otro lado.

Answer 1

Me las arreglé para llegar hasta con una combinatoria de prueba de la declaración en t.b.'s comentario. Me parece que es un argumento similar se resuelve el problema original. De todos modos, vamos a de $n$ ser un entero positivo. Vamos a probar que $$n^{2n+1} > (n-1)^n(n+1)^{n+1}.$$ Después de multiplicar por medio de $n$ y la realización de algunas trivial (aunque ligeramente arcano) manipulaciones, vemos que esto es equivalente a probar $$(n^2)^{n+1} > (n^2-1)^{n+1} + (n+1) \cdot (n^2-1)^n.$$ Ahora para la combinatoria (ver declaración del problema de la notación). El LHS cuenta las funciones en $S_{n+1,n^2}$. El RHS cuenta sólo las funciones en $S_{n+1,n^2}$ que no toma el valor de 1 $$(a través del primer término) o de lo contrario toma el valor de 1$$ exactamente una vez (a través del segundo plazo). Y, bueno, eso es todo!!

---

Añadido: Bueno creo que me di cuenta de cómo hacer el problema original en el mismo tipo de camino. La combinatoria de paso es un poco más torpe, por alguna razón. Tal vez alguien más puede ver de una mejor manera? Como antes, y mucho $$n sea un entero positivo. Vamos a probar que$$ (n-1)^{n-1}(n+1)^n > n^{2n-1}. $$Multiplicar por $n-1$, esto se convierte en$$ (n^2 -1)^n > (n^2)^n - n \cdot (n^2)^{n-1} $$o, de manera equivalente,$$ (n^2 -1)^n + n \cdot (n^2)^{n-1} > (n^2)^n. $$Este último obligado puede ser probado de forma combinatoria. En el lado derecho tenemos todas las funciones en $S_{n,n^2}$. El primer término en el lado izquierdo cuenta las funciones en $S_{n,n^2}$, que nunca toma el valor de 1$$ . Deje de $S$ el conjunto de funciones en $S_{n,n^2}$, que hacer toma el valor de 1$$. Tenemos que demostrar $S$ tiene menos de $n \cdot (n^2)^{n-1}$ elementos. Se puede inyectar $S$ en $\{1,\ldots,n\} \times S_{n-1,n^2}$ por envío de $f \in S$ a la par de $(x,f_x)$ donde $x$ es el miembro más pequeño de $\{1,\ldots,n\}$ con $f(x) = 1$, y $f_x$ se obtiene a partir de $f$ por "saltar" de más de $x$ (con el fin de obtener una función con un menor elemento en el dominio). En fin, a ver que la desigualdad es estricta, tenga en cuenta que (creo que tal vez suponiendo que $n \geq 2$) $(n,1)$ no está en el rango de esta inyección ($1$ es la función constante). Esto completa la prueba.

Answer 2

Esta no es la combinatoria, pero mi favorita es la prueba de N. S Mendelsohn, "Una aplicación de un famoso de la desigualdad", Amer. De matemáticas. Mensual 58 (1951), 563.

El uso de la prueba de la aritmética-media geométrica de la desigualdad (AGMI) en el formulario $(\frac{1}{n}\sum_{i=1}^n a_i)^n \ge \prod_{i=1}^n a_i$ con la desigualdad de ser estricto, si no todas las $a_i$ son iguales.

Considerar $n$ los valores de $1+1/n$ y 1 el valor de 1. Por los AGMI, $((n+2)/(n+1))^{n+1} > (1+1/n)^n$, o $(1+1/(n+1))^{n+1} > (1+1/n)^n$.

Considerar $n$ los valores de $1-1/n$ y 1 el valor de 1. Por los AGMI, $(n/(n+1))^{n+1} > (1-1/n)^n$ o $(1+1/n)^{n+1} < (1+1/(n-1))^n$.

Una nota interesante es que esto se utiliza la versión de los AGMI en el que $n-1$ de la $n$ los valores son los mismos, que puede ser mostrado implica la desigualdad de Bernoulli ($(1+x)^n \ge 1+nx$ para $x \ge 0$ y entero $n \ge 1$).

Answer 3

Creo que la siguiente función $\Phi \colon S_{n,n} \times S_{n,n+2} \times S_{1,n+2} \S_{n,n+1} \times S_{n,n+1} \times S_{1,n+1}$ es un surjection, lo cual sería el deseado desigualdad. Cada elemento del dominio y el rango de $\Phi$ es una función $\{1,\dots,n\} \cup \{1,\dots,n\} \cup \{1\}$; por el bien de nuestra cordura vamos a escribir esto como $\{1_a,\dots,n_a\} \cup \{1_b,\dots,n_b\} \cup \{1_c\}$.

Dado $f\in S_{n,n} \times S_{n,n+2} \times S_{1,n+2}$, definimos $\Phi(f) \S_{n,n+1} \times S_{n,n+1} \times S_{1,n+1}$ como sigue. (En adelante, $j$ siempre denota un número entero entre $1$ y $n$.)

• Si $f(1_c) \ne n+2$, a continuación, establezca:
  • $\Phi(f)(j_a) = \begin{casos} f(j_a), & \text{si } f(j_b) \ne n+2, \\ n+1, & \text{si } f(j_b) = n+2. \end{casos}$
  • $\Phi(f)(j_b) = \begin{casos} f(j_b), & \text{si } f(j_b) \ne n+2, \\ f(j_a), & \text{si } f(j_b) = n+2. \end{casos}$
  • $\Phi(f)(1_c) = f(1_c)$.
• Si $f(1_c) = n+2$ y existe $1\le j\le n$ tal que $f(j_b) \ge n+1$, entonces que $k$ ser el menos $j$; a continuación, establezca:
  • $\Phi(f)(j_a) = \begin{casos} f(j_a), & \text{si } f(j_b) \le n, \\ n+1, & \text{si } f(j_b) \ge n+1. \end{casos}$
  • $\Phi(f)(j_b) = \begin{casos} f(j_b), & \text{si } f(j_b) \le n, \\ n+1, & \text{si } f(j_b) \ge n+1. \end{casos}$
  • $\Phi(f)(1_c) = \begin{casos} f(k_a), & \text{si } f(k_b) = n+1, \\ f(k_a)+1, & \text{si } f(k_b) = n+2. \end{casos}$
• Si $f(1_c) = n+2$ pero no existe $1\le j\le n$ tal que $f(j_b) \ge n+1$, entonces no me importa lo que $\Phi(f)$ es.

La primera parte de la construcción abarca cada función $g \in S_{n,n+1} \times S_{n,n+1} \times S_{1,n+1}$, excepto aquellos para los cuales no existe $j$ tales que $g(j_a) = g(j_b) = n+1$; la segunda parte (ojalá) cubre estas funciones especiales de $g$.