The number of zeros of a polynomial that almost changes signs Let $p$ be a polynomial, and let $x_0, x_1, \dots, x_n$ be distinct numbers in the interval $[-1, 1]$, listed in increasing order, for which the following holds:
$$
(-1)^ip(x_i) \geq 0,\hspace{1cm}i \in \{0, 1, \dots, n\}
$$
Is it the case that $p$ has no fewer than $n$ zeros, either distinct or coincident? (If the inequality were strict, the answer would be "yes", by the intermediate value theorem.)
 A: Counting the zeros with multiplicity, the answer is still yes. If $p$ is a (real) polynomial, and $x_0 < x_1 < \dotsc < x_n$ are points such that $(-1)^i p(x_i) \geqslant 0$ for $0 \leqslant i \leqslant n$, then $p$ has at least $n$ zeros in the interval $[x_0,x_n]$ counted with multiplicity.
We prove that by induction on $n$, modifying the proof for the case of strict inequalities. The important fact is that at a simple zero, $p$ changes its sign. That allows to deduce the existence of further zeros or multiple zeros in certain configurations.
The base case $n = 1$ is direct, either (at least) one of $p(x_0)$ and $p(x_1)$ is $0$, or we have $p(x_0) > 0 > p(x_1)$ and the intermediate value theorem asserts the existence of a zero in $(x_0,x_1)$.
For the induction step, we have $x_0 < x_1 < \dotsc < x_n < x_{n+1}$, and the induction hypothesis asserts the existence of at least $n$ zeros of $p$ in the interval $[x_0,x_n]$. If $p(x_{n+1}) = 0$, we have found our $n+1^{\text{st}}$ zero and we're done. So in the following, we consider the case $(-1)^{n+1}p(x_{n+1}) > 0$. If $(-1)^np(x_n) > 0$, then $p$ has a further zero strictly between $x_n$ and $x_{n+1}$, and again we have our $n+1^{\text{st}}$ zero. If $p(x_0) = p(x_1) = \dotsc = p(x_n) = 0$, these are $n+1$ zeros, and we are done again.
Finally, we are looking at the situation where $(-1)^kp(x_k) > 0$, $(-1)^{n+1}p(x_{n+1}) > 0$ and $p(x_{k+1}) = \dotsc = p(x_n) = 0$. By hypothesis, we have at least $k$ zeros of $p$ in the interval $[x_0,x_k)$, and by assumption, we have $n-k$ distinct zeros of $p$ in the interval $(x_k,x_{n+1})$. We must see that there is an additional zero in that interval, or (at least) one of the $x_i$ is a multiple zero. If the $x_i,\; k < i \leqslant n$ were all simple zeros, and there were no other zero of $p$ in the interval $(x_k,x_{n+1})$, then there would be precisely $n-k$ sign changes of $p$ between $x_k$ and $x_{n+1}$, hence
$$(-1)^{n-k}p(x_k)p(x_{n+1}) > 0.\tag{A}$$
But in the situation we are considering, we have
$$(-1)^kp(x_k) > 0 \land (-1)^{n+1}p(x_{n+1}) > 0,$$
which implies
$$(-1)^{n-k+1}p(x_k)p(x_{n+1}) = \bigl((-1)^kp(x_k)\bigr)\cdot \bigl((-1)^{n+1}p(x_{n+1})\bigr) > 0.\tag{B}$$
But $(\text{B})$ contradicts $(\text{A})$, so we conclude the existence of a further zero of $p$ in $(x_k,x_{n+1})$ (either distinct from the $x_i$ or in the form of a multiple zero at one of the $x_i$).
