Positivity of a certain sum of Stirling numbers
Past days I've been trying to prove that certain polynomials have positive coefficients. After a lot of thinking, I came up with a formula for each coefficient individually, and they are not that ugly. I think maybe someone can give me a hand on this.
Synthetically, what I want to prove is that the following sum is positive:
$$S(k,n,m)=\sum_{i=0}^{n-m-1} \sum_{j=0}^{k-1} (-1)^{i+j} \binom{n}{j}(k-j)^m {j \brack {j-i}} {{n-j}\brack {m+1+i-j}}$$
Where the symbol ${x \brack y}$ stands for the Stirling numbers of the first kind (without sign).
I'm interested in the case $1\leq m,k\leq n-1$.
I have already proven the following:
1) If in the sum we set $m=n-1$, we get just the well known recurrence for Eulerian numbers, so it is positive. For $m=n-2$, the result is a sum of two Eulerian numbers.
2) If we replace $k$ by $n-k$, the sum remains the same.
3) With $k=1$, we get simply the Stirling numbers of the first kind.
4) With $m=1$ the sum is always positive.
Probably someone with more experience working on this kind of sums can give me a hand. I bet that there may be even a way to understand this sum combinatorially.
For the moment at least, I can just individuate the first step of an approach which might be possibly interesting.
The sum can be rewritten as $$ \eqalign{ & S(q,n,m) = \sum\limits_{\left( {0\, \le } \right)\,\,i\,\,\left( { \le \,n - m - 1} \right)} {\;\sum\limits_{\left( {0\, \le } \right)\,j\, \le \,q - 1} {\left( { - 1} \right)^{\,i + j} \left( \matrix{ n \cr j \cr} \right)\left( {q - j} \right)^{\,m} \left[ \matrix{ j \cr j - i \cr} \right]\left[ \matrix{ n - j \cr m + 1 + i - j \cr} \right]} } = \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,m + 1} \right)} {\;\sum\limits_{\left( {0\, \le } \right)\,j\, \le \,q - 1} {\left( { - 1} \right)^{\,k} \left( \matrix{ n \cr j \cr} \right)\left( {q - j} \right)^{\,m} \left[ \matrix{ j \cr k \cr} \right]\left[ \matrix{ n - j \cr m + 1 - k \cr} \right]} } = \cr & = \sum\limits_{\left( {0\, \le } \right)\,j\, \le \,q - 1} {\left( \matrix{ n \cr j \cr} \right)\left( {q - j} \right)^{\,m} \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,m + 1} \right)} {\left( { - 1} \right)^{\,k} \left[ \matrix{ j \cr k \cr} \right]\left[ \matrix{ n - j \cr m + 1 - k \cr} \right]} } \cr} $$ where putting the bounds in parentheses is meant to underline that they are implicit in the binomial / Stirling n. , which is a useful indication for dealing with convolutions.
Since
$$
x^{\,\overline {\,n\,} } x^{\,\overline {\,m\,} } = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n + m} \right)} {\sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,k} \right)}
{\left[ \matrix{ n \cr
j \cr} \right]\left[ \matrix{
m \cr
k - j \cr} \right]x^{\,k} } }
$$
where $x^{\,\underline {\,k\,} } ,\quad x^{\,\overline {\,k\,} } $ represent respectively the
Falling and Rising Factorial
then the inner sum above can be written as
$$
\eqalign{
& \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,m + 1} \right)}
{\left( { - 1} \right)^{\,k} \left[ \matrix{ j \cr k \cr} \right]\left[ \matrix{ n - j \cr m + 1 - k \cr} \right]}
= \left[ {x^{\,m + 1} } \right]\left( {\left( { - x} \right)^{\,\overline {\,j\,} } x^{\,\overline {\,n - j\,} } } \right) = \cr
& = \left[ {x^{\,m + 1} } \right]\left( {\left( { - 1} \right)^j x^{\,\underline {\,j\,} } x^{\,\overline {\,n - j\,} } } \right)
= \left[ {x^{\,m + 1} } \right]\left( {\left( { - 1} \right)^j x^{\,\underline {\,j\,} } \left( {x + n - 1 - j} \right)^{\,\underline {\,n - j\,} } } \right)
\quad \left| \matrix{ \;1 \le n \hfill \cr \;j \le n \hfill \cr} \right. \cr}
$$
thus giving
$$ \bbox[lightyellow] {
S(q,n,m) = \left[ {x^{\,m + 1} } \right]\sum\limits_{\left( {0\, \le } \right)\,j\, \le \,q - 1} {\left( { - 1} \right)^j
\left( \matrix{ n \cr j \cr} \right)
\left( {q - j} \right)^{\,m} x^{\,\underline {\,j\,} } x^{\,\overline {\,n - j\,} } } \quad \left| {\;1 \le n} \right.
}$$
The function on RHS can be further rewritten as $$ \eqalign{ & F(q,n,m,x) = \sum\limits_{\left( {0\, \le } \right)\,j\, \le \,q - 1} {\left( { - 1} \right)^j \left( \matrix{ n \cr j \cr} \right)\left( {q - j} \right)^{\,m} x^{\,\underline {\,j\,} } x^{\,\overline {\,n - j\,} } } = \cr & = n!\sum\limits_{\left( {0\, \le } \right)\,j\, \le \,q - 1} {\left( { - 1} \right)^j \left( {q - j} \right)^{\,m} \left( \matrix{ x \cr j \cr} \right)\left( \matrix{ x + n - 1 - j \cr n - j \cr} \right)} = \cr & = n!\sum\limits_{\left( {0\, \le } \right)\,j\, \le \,q - 1} {\left( {q - j} \right)^{\,m} \left( \matrix{ j - x - 1 \cr j \cr} \right)\left( \matrix{ x + n - 1 - j \cr n - j \cr} \right)} \cr} $$