Descartes' rule of signs

From ProofWiki
Jump to: navigation, search

Statement

The rule states that if the terms of a single-variable polynomial with real coefficients are ordered by descending variable exponent, then the number of positive roots of the polynomial is either equal to the number of sign differences between consecutive nonzero coefficients, or is less than it by an even number. Multiple roots of the same value are counted separately.

Theorem: Let \( f(x) = a_nx^n + a_{n-1}x^{n-1}+ \cdots+a_0\) be a polynomial with real coefficients. Let \( s\) be the number of sign changes in the sequence \( a_n,a_{n-1},\ldots,a_0\): that is, delete the terms of the sequence that are \( 0,\) and let \( s \) be the number of pairs of consecutive terms in the remaining sequence that have opposite signs. Let \( p \) be the number of positive roots of \( f(x) \) (counted with multiplicity). Then \( s-p \) is a nonnegative even number.


Proof (using induction)

Base case: For f(x)=ax+b, we have the only root \( x_{0}=-\frac{b}{a}\) and so s-p=0.

Inductive case Suppose that n-1 degree polynomials satisfy s-p=even nonnegative number.

First we prove that s-p is an even number. WLOG assume that \(a_{n}\) is positive. We split cases over f(0). If \(a_{0}:=f(0)>0\), then we claim that there are even number of sign changes and even number of positive roots.

We have the following cases for \(a_{n}\cdot a_{n-1}\) and \(a_{1}\cdot a_{0}\). If these terms have the same parity (sign change at both ends, or no sign change at both ends), then we are reduced to the n-1 polynomial by ignoring the \(a_{n},a_{0}\) terms. If the terms have different parity (sign change at one end but not the other), then we ignore the term where the sign change happen to get a reduced polynomial. In particular, suppose that \(a_{n-1}<0\), then we ignore the \(a_{n}\) term and all the lower order terms \(a_{0},a_{1},...,a_{d}\) that are nonnegative till we get a negative term \(a_{d+1}<0\), and so we reduced to a lower order polynomial. Therefore, s is even.

Since \(a_{n},a_{0}>0\) we have that the function starts positive at 0 and eventually grows to positive infinity. So either we have no positive roots or an even number of them. Therefore, p is even.

The case \(a_{0}:=f(0)<0\) is similar for showing that s is odd. For showing that p is odd, we have that f(0)<0 and the polynomial grows to positive infinity, so it must have at least one positive root.

Second, we prove that \(s\geq p\). We will use that the derivative f' is an (n-1) degree polynomial and let s' be the number of its sign changes and p' the number of its positive roots. Since f and f' have the same parity for each of their terms besides \(a_{0}\), we have \(s\geq s'\). If f has p positive roots, then by Rolle's theorem f' has at least p-1 positive roots. Therefore, together we have \begin{align*} s\geq s'\stackrel{Induction}{\geq }p'\geq p-1. \end{align*} So \(s-p\geq -1\) but since s-p is an even number, we obtain \(s\geq p\).