Desigualdad de los números de Stirling del primer tipo

Question

Por cada $n\geq1$ hay algo de $f(n)$ tal que para los números de Stirling del primer tipo tenemos:

$c(n,0)<c(n,1)<...<c(n,f(n)-1)\leq c(n,f(n))>c(n,f(n)+1)>...>c(n,n)$

Además, $f(n)=f(n-1)$ o $f(n)=f(n-1)+1$ .

No estoy seguro de por dónde empezar, ya que no sé lo que el $f(n)$ podría ser. Me parece que va a ser una prueba generativa y no combinatoria; quizá haya dos pruebas, pero la generativa podría ser más fácil. ¿Cómo lo planteo?

Answer 1

Demostraremos, por inducción en $n$ la existencia de un número entero $f(n)$ de forma que se cumplan estas tres condiciones:

• para cada $k\in \{1,2,\dots,f(n)-1\}$ tenemos $c(n,k)-c(n,k-1)>0$ ,

• $c(n,f(n))-c(n,f(n)-1)\ge 0$ ,

• para cada $ k\in \{f(n)+1,f(n)+2,\dots,n\}$ tenemos $c(n,k)-c(n,k-1)<0$ .

El caso base es obvio, así que pasemos al paso de inducción. Supongamos que $f(n)$ existe. Queremos demostrar $f(n+1)$ existe, por lo que consideramos las diferencias $c(n+1,k)-c(n+1,k-1)$ . Nota $$ \begin{align} c(n+1,k)-c(n+1,k-1) &= [c(n,k-1)+n\,c(n,k)]-[c(n,k-2)+n\,c(n,k-1)] \\ &= [\color{blue}{c(n,k-1)-c(n,k-2)}]+n\cdot[\color{green}{c(n,k)-c(n,k-1)}] \end{align} $$ Concluya de la siguiente manera:

• Para todos $k\le f(n)$ la hipótesis de inducción implica que la diferencia verde es no negativa y la diferencia azul es positiva. De ello se deduce que $c(n+1,k)-c(n+1,k-1)>0$ para $k\le f(n)$ .

• Para todos $k\ge f(n)+2$ la hipótesis de inducción implica que las diferencias azul y verde son ambas negativas. De ello se deduce que $c(n+1,k)-c(n+1,k-1)<0$ para $k\ge f(n)+2$ .

• La única diferencia que queda por considerar es cuando $k=f(n)+1$ .

  • Si $c(n+1,f(n)+1)-c(n+1,f(n))<0$ hemos demostrado $f(n+1)=f(n)$ .

  • Si $c(n+1,f(n)+1)-c(n+1,f(n))\ge 0$ hemos demostrado $f(n+1)=f(n)+1$ .

En cualquier caso, hemos demostrado $f(n+1)$ existe, y que es igual a $f(n)$ o $f(n)+1$ .