# Prove that a particular polynomial sequence is a Sturm sequence

Let us define the following sequence of polynomials for every two non-negative integers $i,d$: $$s_i^d(w)=\sum_{j=0}^{d+1} (-1)^j {d+1\choose j} (j+1)^i w^{d+1-j}.$$ Conjecture: The sequence $\{s_d^d(w),s_d^{d-1}(w),\dots,s_d^0(w)\}$ is a Sturm sequence.

An easy corollary of this conjecture is that:

Corollary: For $i\geq d$, the roots of the polynomial $s_i^d(w)$ are all real, simple (and positive).

Any idea how to prove either the Conjecture or (directly) the Corollary? Or, in the worst case, the Corollary for the special case $i=d$?

Note that:

1. $s_0^d(w)=(w-1)^{d+1}$
2. $s_i^0(w)=w-2^i$
3. ${d\over dw} s_i^d(w)=(d+1)s_i^{d-1}(w)$.
-
In what context do these polynomials appear? If you remove the (-1)^j part, it should still be a Sturm sequence, but with non-negative coefficients. Do these coefficients count something? –  Per Alexandersson Oct 17 '12 at 19:25
Shouldn't property 3 have just the factor $(d+1)$, without factorial? –  Pietro Majer Oct 17 '12 at 22:46
@Pietro Majer: yes absolutely, corrected. Thanks! –  dima Oct 18 '12 at 10:02
@Peter: of course, just corrected. –  dima Oct 18 '12 at 10:12
These polynomials appear as first-order approximations in some nonlinear reconstruction problems, see e.g. arxiv.org/abs/1005.1884. If we substitute $t=-w$ we get a polynomial with positive coefficients and preserving the multiplicities of the roots. So, if positive-coefficient sequence is Sturm, it should be sufficient for our purposes. –  dima Oct 18 '12 at 15:26

This is just a partial answer, but anyway: ( I use $s[n,k]$ for $s^n_k$ since I just copy-pasted from Mathematica:

I do not know if this helps, or if you already know, but you have the recurrence $$s[n- 1,k + 1] = s'[n, k] - x \cdot s'[n - 1, k]$$

Note, by induction, we assume $s[n,k]$ and $s[n-1,k]$ to have interlacing roots. By thm 1.47 in http://arxiv.org/abs/math/0612833 (look into this work), we know that the derivatives have interlacing roots as well.

Now, the recursion is quite similar to many other that appear in the link above, so it might not be too hard to prove stability.

EDIT: I show/sketch below that the operator $f \mapsto A f - x f'$ always produce roots interlaced (and to the right) of the roots of $f$, provided $A>\deg f$ and that all roots of $f$ are positive. (We may assume leading term of $f$ has positive coefficient).

Clearly if f has a root of multiplicity m, then the result will have the same root with multiplicity m-1, so the problem is essentially to ensure that no new multiple roots may appear.

Assume now we have two consecutive roots $0\le a \le b$ of $f$ and that $f$ is positive between these. The derivative of $f$ this first positive, and then negative in $[a,b]$, thus $-x f'$ is first negative and then positive. Hence, $A f - x f'$ is negative in $a$, and positive in $b.$ Thus, we have a root of $A f - x f'$ in the interval $[a,b]$. (Mutatis mutandis for the case when f is negative between $a$ and $b$).

Now, if the degree of $f$ is even, $f$ is positive to the right of its largest root. The derivative is also positive here (since even degree poly), so $x f'$ is positive. Hence, $A f - x f'$ is negative in this point. However, notice this is a polynomial with even degree, and with a leading coefficient! Hence, it must eventually cross the real line and grow to infinity. (Mutatis mutandis for the case when f is odd).

This proves that $f \mapsto A f - x f'$ produces interlacing roots, and eventual multiplicities are decreased, no new multiple roots can be introduced.

-
@Per: did you just guess the recurrence? –  dima Oct 18 '12 at 11:48
what is the induction basis? If it's $\{n=0,1; k=0\}$, then the inductive argument doesn't help to prove the interlacing for $n>0$ (one cannot take the basis to be $\{n=0,1,…,d;k=0\}$ since $s^d_0=(x−1)^{d+1}$ and therefore no interlacing between $s^{d−1}_0$ and $s^d_0$). –  dima Oct 18 '12 at 11:50
Rewrite the recurrence as $$s_{i+1}^d(w)=(d+2)s_i^d(w)-ws'_i^d(w)$$ Now by [Polya & Szego, Vol. 2, Part 5, Problem 66] we have that $s_{i+1}^d$ has no more imaginary roots than $s_i^d$. But $s_0^d=(w-1)^{d+1}$, therefore $s_i^d$ has only real roots for all $i\geq 0$. The only thing left is to show that $s_d^d$ has no multiple roots. –  dima Oct 18 '12 at 12:58
Yes, I just guessed; I have no proof of it, but since you have an explicit formula, I guess it is straightforward to prove. Seems like you are almost there now. –  Per Alexandersson Oct 18 '12 at 16:00
Indeed the proof of the recurrence is straightforward. However this last step (proving that $s^d_d$ is square-free) is right now elusive. –  dima Oct 18 '12 at 16:23