Sign changes of a polynomial Assume we have a polynomial $p(x)\in\mathbb{R}[x]$ that all of its roots are real. I think sum of sign changes of coefficients of $p(x)$ and $p(-x)$ is equal to or less than the degree of the polynomial, but I couldn't show it. Can anyone help me to show it or bring a counterexample for this?
 A: There is a more general fact;
Number of sign changes of $p(x)$ and $p(-x)$ together can be less than or equal to the degree of $p(x)$.
We will prove this using an induction. Assume for polynomials with degree less than $n$, it's true. Now consider $$p(x)=a_nx^n+\cdots+a_{d+1}x^{d+1}+a_dx^{d}+\cdots+a_1x+a_0$$
Where $d$ is the first coefficient that its sign is different from sign of $a_n$.
$$\begin{array}{ll}
a_nx^n+\cdots+a_{d+1}x^{d+1}+ & a_dx^{d}+\cdots+a_1x+a_0\\
a_n(-x)^n+\cdots+a_{d+1}(-x)^{d+1}+ & a_d(-x)^{d}+\cdots+a_1(-x)+a_0
\end{array}$$
Sum of number of sign changes of $p(x)$ and $p(-x)$ is sum of sign changes of $q(x)$ and $q(-x)$ where $q(x)=a_dx^{d}+\cdots+a_1x+a_0$ (which as $d<n$ by our induction assumption is less than or equal to $d$) with Number of sign changes of $h(x)$ and $h(-x)$ where $h(x)=a_nx^n+\cdots+a_{d+1}x^{d+1}$ and 1 (1 because of sign of $a_{d+1}$ and $a_d$ is different (but pay attention then $(-1)^{d+1}a_{d+1}$ and $(-1)^da_d$ have same signs). Number of sign changes of $h(x)$ is $0$ and number of sign changes of $h(-x)$ is at most number of its term minus one which is less than or equal to $n-d-1$. Therefore
$$\text{Number of sign changes of $p(x)$ and $p(-x)$}\;\leq d+(n-d-1)+1=n$$
A: Your observation is correct. Note that the number of sign changes cannot be less than the degree (unless you have a (multiple) root at zero, but this is easy to remedy (just factor out the highest possible power of $x$).
The reason is that Descartes' bound is sharp if the polynomial has only real roots. One possible (stronger) argument to see this are the partial converses due to Obreshkoff. It is a collection of theorems which give information about which roots can or cannot be "recognized" by Descartes' rule. In particular, if you consider the positive real line (that is, count the number $v$ of sign changes of $p(x)$), then Obreshkoff's theorem states that $v$ is at least the number of positive real roots of $p$, and at most $\deg p$ minus the number of negative real roots of $p$. If all roots of $p$ are real, this means that you will count the exact number of roots.
There are (IMHO) more intuitive formulations of Obreshkoff's results after projective transformations of the complex plane, which give you local statements for intervals on the real line. For details, have a look at Arno Eigenwillig's PhD thesis (section 2.1) and the references therein.
A different argument which is quite natural is the sign (variation) diminishing property (see, e.g.: ibid, proposition 2.26), which is especially intuitive if you count the sign variations in the Bernstein basis w.r.t. some interval (which, again, are known to be equivalent to the sign changes in the monomial basis). If you consider an interval comprising all roots, then by Descartes' rule of signs (or it's brethren Fourier-Budan, etc...), you count at least as many sign changes as there are real roots. And if all roots are real, you count exactly, since the number of sign changes obviously cannot be higher than the degree.
Now, when splitting at an arbitrary point (0 in your case), the sign variation diminishing property yields that the sign changes for the left (negative) and the right (positive) side sum up to at most this number. But since you have to account for at least all real roots, the inequality is tight for the case of only real roots.
By the way, the result you are after is a byproduct of the direct proofs of Descartes' rule of signs (in particular Gauss' proof, IIRC). The reason why the parity of sign changes and number of roots is the same is that there might be pairs of conjugate complex roots which are either accounted for as two sign changes or not. If there are no complex roots, well, that part is vain.
That's just to say, my explanations above may be intuitive (or not), but also a detour from the rule of signs to a powerful theorem about that rule, and back to an ingredient of the proof of the basic rule.
