$f(x)=a_n x^n + a_{n-1}x^{n-2} +a_{n-2}x^{n-2}+\ldots+a_1 x+a_0$ Descartes' Rule of Signs is a theorem that states that the [[difference]] $s-p$ between $s$ the number of sign-changes in the [[sequence]] of [[coefficients]], and $p$, the actual number of [[Positive|positive]] [[roots]] of a [[polynomial]] $f(x)$, is always a [[Non-Negative|non-negative]] [[even]] number. In the cases where $s<2$ this is especially useful, since $p=s$. Counting sign-changes in the sequence of coefficients refers to counting how many times the sign of the coefficient changes as we go from one term to the next. It's important to note that $p$ counts roots with multiplicity the number of times their multiplicity suggests. --- For example, if we have the polynomial $f(x) = x^3 - 4x^2 + 6x - 8$, - the sequence of coefficients is $(1, -4, 6, -8)$, - and the sequence of their signs is $(+,-,+,-)$. We can see that: - the sign of the coefficient changes from positive to negative at the second term, - and from negative to positive at the third term, - and finally from positive to negative at the fourth term. Therefore, in this case, the number of sign-changes is 3. --- ### Proof $f(x)=a_n x^n + a_{n-1}x^{n-2} +a_{n-2}x^{n-2}+\ldots+a_1 x+a_0$ The first is to show that $s-p$ is even; the second is to show that it is nonnegative. $s$ represents the number of times the $x$-axis is crossed on a [[continuous path]] between $(0,a_0)$ some arbitrary point $(b,f(b))$, such that $b$ is not less than any of the roots. $f(b)$ would have to have the same sign as $a_n$, because of the [[end behavior]] - when $a_n$ and $a_0$ have the same sign, the $x$-axis is not between them, so the number of times it will be crossed must be even. $p$ would be even in this case. - the sequence of signs $(+,\ldots,+)$ may contain adjacent sub-sequences of all negatives. - Each of these sub-sequences introduce exactly two sign-changes: $(+,\ldots, {\color{red}{+},-},\ldots,{\color{red}-,+},\ldots,+)$ - $s$ is even in this case - when $a_n$ and $a_0$ have opposite signs, the $x$-axis is between them, so the number of times it will be crossed must be odd. $p$ would be odd in this case. - the sequence of signs $(+,\ldots,-)$ will contain at least one adjacent sub-sequence of all negatives; the guaranteed one is the last one. - Any adjacent sub-sequences of negatives that are not the final one introduce exactly two sign-changes: $(+,\ldots, {\color{red}{+},-},\ldots,{\color{red}-,+},\ldots,-)$ - The final adjacent sub-sequence of negatives only introduces one sign change at the beginning: $(+,\ldots, {\color{red}{+},-},\ldots,-)$ - $s$ is odd in this case For both cases, the [[parity]] of $s$ and $p$ match, so $s-p$ is certainly even --- To show that $s \geq p$, induct on $n$. The base case $n=1$ is clear. Suppose that all polynomials of degree $n-1$ satisfy $s \geq p$, and take a polynomial $f(x)$ of degree $n$. Consider the polynomial $f^{\prime}(x)$ of degree $n-1$. The number of sign changes $s^{\prime}$ of $f^{\prime}(x)$ is either $s$ or $s-1$, depending on whether there is a signange at the rightmost coefficient of $f$. But the number of positive zeroes $p^{\prime}$ of $f^{\prime}(x)$ is at least $p-1$ by Rolle's theorem, since between any two zeroes of $f$ there is a zero of $f^{\prime}$. Since $f^{\prime}(x)$ has degree $n-1$, the inductive hypothesis implies that $s^{\prime} \geq p^{\prime}$, but then $ s \geq s^{\prime} \geq p^{\prime} \geq p-1 $ so $s-p>-1$, but $s-p$ is even, so it must be nonnegative. This proves the theorem by induction.