**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.



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?
**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](http://matthewhr.files.wordpress.com/2013/09/descartes-rule-of-signs.pdf). $\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](http://www.cut-the-knot.org/fta/ROS2.shtml). $\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.


