Para todos los enteros positivos $n$, $p(n)$ es el número de particiones de $n$ como la suma de enteros positivos (los números de partición); por ejemplo, $p(4)=5$ desde $4=1+1+1+1=1+1+2=1+3=2+2=4.$
Probar que: $\dfrac{1+p(1)+p(2) + \dots + p(n-1)}{p(n)} \leq \sqrt {2n}.$
Este problema es de un turco concurso. Tal vez es un resultado conocido.
Más información acerca de los números de partición se puede encontrar en OEIS.
Cualquier ayuda se agradece.
Respuesta
¿Demasiados anuncios?
Damos una prueba de la desigualdad estricta $$ \frac{1 + p(1) + p(2) + \cdots + p(n-1)}{p(n)} < \sqrt{2n}. $$ La raíz cuadrada surge por primera demostrando un límite superior $(k-1)/2 + (n/k)$ para cualquier entero $k \geq 1$, y, a continuación, minimizando $k$; este tipo de cosa es visto a menudo en el análisis, pero no es una táctica común en las desigualdades que aparecen en la competencia matemática.
Es conveniente y natural para extender la definición de $p(n)$ para todos los enteros mediante el establecimiento $p(n) = 0$ todos los $n < 0$$p(0) = 1$. En particular, el numerador $1 + p(1) + p(2) + p(3) + \cdots$ en la fracción de interés es $$ s_1 := \sum_{n' < n} p(n') = \sum_{m=1}^\infty p(n-m). $$ A continuación, para todos los $n$ $p(n)$ particiones de $n$ puede ser identificado con soluciones de $$ n = \sum_{i=1}^\infty me a_i = a_1 + 2 a_2 + 3 a_3 + 4 a_4 + \cdots $$ en números enteros no negativos $a_i$ que se desvanecen para todos, pero un número finito de $i$. (Cada una de las $a_i$ es el número de veces que $i$ se produce en la partición). De curso $p(n)$ es la suma de $1$ más de este tipo de soluciones $(a_1,a_2,a_3,\ldots)$. El primer punto clave es:
Lema 1. $s_1$ es la suma de $a_1$ más de particiones $(a_1,a_2,a_3,\ldots)$$n$.
Esto puede ser demostrado mediante la generación de funciones, o combinatoria de
Lema 2. $p(n) - p(n-1)$ es el número de particiones $(a_1,a_2,a_3,\ldots)$$n$$a_1 = 0$.
La prueba: Las particiones con $a_1 > 0$ están en bijection con el particiones de $n-1$$(a_1,a_2,a_3,\ldots) \mapsto (a_1-1,a_2,a_3,\ldots)$. $\Box$
(Corolario 1: $p(n) \geq p(n-1)$ todos los $n$, con igualdad de iff $n=1$.)
Ahora Lema 1 se puede demostrar mediante la bijecting, para cada una de las $m$, el particiones de $n$ $a_1 = m$ con particiones de $n-m$$a_1=0$, y sumando más de $m$.
El siguiente punto es generalizar Lema 1 con una fórmula para la suma de $a_i$ sobre las particiones de $n$:
Lema 3. Para $i \geq 1$ definir $$ s_i := \sum_{m=1}^\infty p(n-im). $$ A continuación, $s_i$ es la suma de $a_m$ sobre las particiones $(a_1,a_2,a_3,\ldots)$$n$.
Prueba como antes, generalizando el Lema 2: $p(n) - p(n-i)$ es el número de particiones $(a_1,a_2,a_3,\ldots)$ $n$ con $a_i = 0$. $\Box$
Lema 4. $\sum_{i\geq 1} i s_i = n p(n)$.
Prueba: Por el Lema 3 $\sum_{i\geq 1} i s_i$ es la suma, de nuevo sobre las particiones de $n$$\sum_i i a_i$, que es $n$. $\Box$
[David Speyer notas en un comentario de que esto también puede ser obtenido a partir de la la generación de la función $\sum_{n\geq 0} p(n) x^n = \prod_{i \geq 1} (1-x^i)^{-1}$, aquí aplicando el operador $x \frac{d}{dx}$.]
Corolario 2. Para cualquier $k$ tenemos $\sum_{i=1}^k i s_i \leq n p(n)$.
Eso es una desigualdad en una combinación lineal de $s_1,\ldots,s_k$. Para llegar a una desigualdad en sólo $s_1$, podemos utilizar:
Lema 5. Para todos los $i\geq 1$ tenemos $s_1 + p(n) \leq i(s_i + p(n))$.
Prueba: tenga en cuenta que $s_i + p(n) = \sum_{i \geq 0} p(n-im)$. Por lo tanto
$ i (s_i + p(n)) = \sum_{i \geq 0} i p(n-im) $
$ \phantom{i (s_i + p(n))} \leq \sum_{i \geq 0} \bigl(p(n-im) + p(n-im-1) + p(n-im-2) + \cdots + p(n-im-(i-1) \bigr)$
$ \phantom{i (s_i + p(n))} = s_1 + p(n),$
usando el Corolario 1 en el medio paso. $\Box$
La combinación de Lema 5 con el Corolario 2 de los rendimientos $$ np(n) \geq \sum_{i=1}^k i s_i \geq \sum_{i=1}^k (s_1 - (i-1) p_n) = k s_1 - {k \elegir 2} p(n), $$ de dónde $$ s_1 \leq \left( \frac{k-1}{2} + \frac{n}{k} \right) p(n). $$ Se queda elegir el entero $k$ a fin de minimizar el límite superior $(k-1)/2 + (n/k)$. El final lema es elemental pero tiene cierta verborrea para probar en su totalidad, y este post ya es bastante largo, así que voy a dejar como un ejercicio:
Lema 6: El valor mínimo de $\frac{k-1}{2} + \frac{n}{k}$ más de enteros $k \geq 1$ es alcanzado iff ${k \choose 2} \leq n \leq {k+1 \choose 2}$. Este es el valor mínimo es menor que $\sqrt{2n}$ todos los $n$.
(Tenga en cuenta que si $n = {\kappa \choose 2}$, entonces hay dos opciones de $k$, es decir,$k=\kappa$$k = \kappa-1$; de lo contrario, la elección es única. Para un gran $n$, el valor óptimo(s) de $k$ crecer(s)$\sqrt{n/2}$, que es de hecho donde $k/2 + n/k$ alcanza su mínimo de $\sqrt{2n}$.)
La combinación de los Lemas 6 con el de la desigualdad de la $s_1$ (que se muestra a continuación Lema 5) los rendimientos de la deseada desigualdad $s_1 / p(n) < \sqrt{2n}$, QED.
