Defining $\{a_i\}$ as $(1+x+⋯+x^k)^n =\sum_{i=0}^{kn}a_ix^i$, then is the 'special' difference-sequence $\{d^Na_i\}$ a unimodal sequence?

Question

Question : Letting $k,n$ be positive integers, let's define a sequence $\{a_i\}\ (i=0,1,\cdots, kn)$ as $$(1+x+\cdots+x^k)^n=\sum_{i=0}^{kn}a_ix^i.$$ Then, is the 'special' difference-sequence $\{d^Na_i\}$ a unimodal sequence for every non-negative integer $N$? If the answer is yes, then prove that. If the answer is no, then find a counterexample.

Definition :

1. Let's call a sequence $\{a_i\}\ (i=0,1,\cdots,kn)$ which satisfies the following condition 'a unimodal sequence'.

Condition : $\ $There exists an integer $t$ such that $$a_0\le a_1\le \cdots\le a_t\ge a_{t+1}\ge a_{t+2}\ge\cdots.$$

2. Let's define $\{d^Na_i\}\ (N\in\mathbb N)$ as the following:

$$d^Na_i=\max(d^{N-1}a_i-d^{N-1}a_{i-1},0)\ \ \ (i=0,1,\cdots, kn),$$ $$d^0a_i=a_i, \ a_{-1}=0.$$

Please note that this is not an usual difference-sequence. (we may call this 'a special difference-sequence')

Motivation :

When I saw Pascal's triangle, I found this property about $a_i=\ _nC_i$. Then, I generalized this property.

Example : Let's see the $(k,n)=(1,8)$ case.

$$a_i(=d^0a_i) : 1\ \ 8\ \ 28\ \ 56\ \ 70\ \ 56\ \ 28\ \ 8\ \ 1$$

$$d^1a_i : 1\ \ 7\ \ 20\ \ 28\ \ 14\ \ 0\ \ 0\ \ 0\ \ 0$$

$$d^2a_i : 1\ \ 6\ \ 13\ \ 8\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0$$

$$d^3a_i : 1\ \ 5\ \ 7\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0$$

$$d^4a_i : 1\ \ 4\ \ 2\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0$$

$$d^5a_i : 1\ \ 3\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0$$

$$d^6a_i : 1\ \ 2\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0$$

$$d^7a_i : 1\ \ 1\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0$$

$$d^Na_i (N\ge 8): 1\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0$$

Hence, we can see that $\{d^N{_8C_i}\}\ (i=0,1,\cdots,8)$ is a unimodal sequence for every non-negative integer $N$.

Remark : This question has been asked previously on math.SE without receiving any complete answers: https://math.stackexchange.com/questions/492651/about-the-unimodality-of-the-coefficients-sequence-of-1x-cdotsxkn

The above definition about 'difference-sequences' might be somewhat unusual, but I won't change its definition. This is because this definition would keep the unimodality. If we define $d^Na_i=d^{N-1}a_i-d^{N-1}a_{i-1} (i=0,1,\cdots)$ as usual, then we get

$$d^1a_i : 1\ \ 7\ \ 20\ \ 28\ \ 14\ \ -14\ \ -28\ \ -20\ \ -7$$

in the above example, which is not unimodal.

Answer 1

UPDATE I now have a complete proof. I'll start with the Pascal's triangle case.

For any sequence of real numbers $r=(r_1, r_2, \ldots, r_k)$, define the number of sign changes of $r$ as follows: Delete all zeroes from $r$, then count how many times the signs of the resulting sequence changes. Recall that Descartes Rule of Signs says that the number of positive roots of $\sum f_k x^k$ is bounded by the number of sign changes of $(f_0, \ldots, f_k)$. My first lemma is a strengthening of Descartes Rule of Signs when all the roots are real.

Claim 1: Let $\sum f_k x^k$ be a polynomial all of whose roots all real. Let $p$ be the number of positive roots, counted with multiplicity. Then the sequence $f_k$ has precisely $p$ sign alternations.

Proof: See, for example, Theorem 1 here. $\square$

Claim 2: Let $f(x) = \sum f_k x^k$ be a polynomial all of whose roots are real. Suppose that $f_i$, $f_{i+1}$, $f_{i+2}$, ..., $f_j$ all have the same sign. Then $f_i$, $f_{i+1}$, ..., $f_j$ is unimodal.

Proof: Let $p$ be the number of positive roots of $f$. By Claim 1, $f_k$ has precisely $p$ sign changes. Define $\ell_0 \leq r_0 < \ell_1 \leq r_1< \ell_2 \leq r_2 < \cdots < \ell_p \leq r_p$ to be the unique indices such that $(-1)^i f_k \geq 0$ for $k \in [\ell_i, r_i]$, and $f_{\ell_i}$ and $f_{r_i}$ are not zero.

Define $g(x) = (1-x) f(x)$. So $g$ has $p+1$ positive roots, and all of its roots are real. Claim 1 tells us that $g_k$ has $p+1$ sign changes. Now, $(-1)^i g_{\ell_i} >0$ and $(-1)^i g_{r_i +1} < 0$. So $g_k$ has a sign change between $\ell_i$ and $r_{i}+1$ for each $i$. There are $p+1$ values of $i$ we can use, and $g_k$ has $p+1$ sign changes, so there must be only one sign change of $g_k$ in each interval $(\ell_i, r_{i}+1)$. Thus, $f$ is unimodal for $k$ in $[\ell_i, r_i]$. $\square$

Let $f(x) = (1+x)^m (1-x)^n$. Let $f_k$ be positive for $0 \leq k \leq r$. (So $r$ is $r_0$ in the terminology of the previous proof.) Since all the roots of $f$ are real, Claim 2 shows that $f_0$, $f_1$, ..., $f_r$ is unimodal. The sequence $(f_0, f_1, \ldots, f_r)$ is precisely $d^m \binom{n}{k}$ in the terminology of the question.

---

UPDATE I can now do the general case. For $f(x)$ a polynomial with real coefficients, let $V(f(x))$ denote the number of sign alternations of the coefficients of $f$.

Lemma $V((1-x) f(x)) \geq V(f(x))+1$.

Proof This is a standard lemma proved in the course of proving Descartes rule of signs. See, for example, this proof. $\square$

Lemma For $m \leq n$, we have $V((1+x+\cdots + x^k)^n (1-x)^m)=m$.

Proof Our proof is by reverse induction. For $m=n$, we have $(1+x+\cdots + x^k)^n (1-x)^m= (1-x^{k+1})^n$ which has $n$ sign alternations. Now assume the lemma for $m$ and we will show that it follows for $m-1$.

By the previous lemma, $V((1+x+\cdots + x^k)^n (1-x)^m) \geq V((1+x+\cdots + x^k)^n (1-x)^{m-1})+1$. So $V((1+x+\cdots + x^k)^n (1-x)^{m-1}) \leq m-1$. But also, $V((1+x+\cdots + x^k)^n (1-x)^{m-1}) \geq V((1+x+\cdots+x^k)^n)+m-1=m-1$. So $V((1+x+\cdots + x^k)^n (1-x)^{m-1})=m-1$ as desired. $\square$

The rest of the argument follows as before. We don't need to go past $m=n$ because, when $m=n$, the truncated partial difference sequence is already shortened to length $1$.

In fact, not only have we shown that these sequences are unimodal, we have shown that they are log convex. Set $h(x) = V((1+x+\cdots + x^k)^n (1-x)^m)$. We showed that the coefficients of $h$ are unimodal in any string of constant sign. But, in fact, the same argument shows $h(rx)$ has the same property for any $r>0$. Saying that $(h_i r^i, h_{i+1} r^{i+1}, \ldots, h_j r^j)$ is unimodal for all positive $r$ is the same as saying that $(h_i, h_{i+1}, \ldots, h_j)$ is log convex.

Answer 2

Yes, because convolutions of log-concave sequences are log-concave. Products of polynomials are convolutions of their coefficient sequence. Search on these keywords and you'll find tons of references.