# Can we prove that an odd degree real polynomial has a root from Descartes' Rule of Signs?

I have been curious about that for some time now, without finding a proof:

It is well-known that a odd degree polynomial $P(x)$ with real coefficients have at least one root. The usual proof use the fact that $\lim_{x\to\infty}P(x)=\pm\infty$ and $\lim_{x\to-\infty}P(x)=\mp\infty$ and the Intermediate Value Theorem.

On the other hand, Descartes' Rule of Signs (DROS) goes like this:

Let $P(x)$ be a polynomial of degree $n$ with real coefficients. Then:

1. The number of positive roots of $P$ is equal to the number $v$ of variations in sign of $P(x)$, or is less than $v$ by an even number.
2. The number of negative roots of $P$ is equal to the number $w$ of variations in sign of $P(-x)$, or is less than $w$ by an even number.

Note: A variation in sign occurs when two consecutive coefficients have an opposite sign. We ignore zero coefficients and roots are counted with multiplicity.

I was wondering if I can use the DROS to prove that odd degree polynomials with real coefficients always have a root. The structure of the proof would be something like that:

1. If $P(0)=0$, we are done. Assume $P(0)\neq 0$.
2. Assume that $P$ has no positive root. Then the number $v$ of variations in sign of $P(x)$ is even.
3. Discussion to show that the number $w$ of variations in sign has to be odd, so that $P$ need to have a (negative) root.

Unfortunately, I have been unable to complete the discussion and the proof.

Any idea? Any proof, hint or reference is welcome.

• You can map the coefficients to their signs, this gives a string consisting of the numbers $1$ and $-1$ where you start with the coefficient of the highest power and end at the constant term. If there are an even number of sign changes then the string decomposes into substrings containing only $1$ of $-1$ such that there are an odd number of such substrings. Changing the sign of $x$ makes the substrings become alternating in $1$ and $-1$ while at the boundaries between substrings there is no change in sign from one to the next substring. – Count Iblis Sep 12 '17 at 4:49
• The number of sign changes in each substring is its length minus 1, so adding this up for all the substrings yields the length of the string minus the number of strings, which is an odd number. This is the total number of sign changes because there are no sign changes between the substrings. – Count Iblis Sep 12 '17 at 4:51
Let's write the polynomial $P(x)$ as:
$$P(x) = \sum_{k=0}^n c_k x^k$$
We assume that $n$ is odd, $c_0 >0$ and $c_n\neq 0$. If the sequence of the coefficients $c_k$ has an even number of sign changes then we want to demonstrate that this implies that the sequence $(-1)^k c_k$ has an odd number of sign changes. What we can do is to decompose the entire sequence as a concatenation of subsequences such that each subsequence contains coefficients of equal sign in the sense that no changes of sign happen in a subsequence (if a coefficient becomes zero then that's not considered to be a change of relative to the previous coefficient). We make the division into subsequences maximal, this then implies that there is always a change of sign between the last element of a subsequence and the first element of the next subsequence.
The number of sign changes is thus equal to the number of subsequences minus 1, therefore the number of subsequences is odd. If we now replace the $c_k$ by $(-1)^k c_k$, then the changes of sign from each last element of a subsequence to the first element of the next subsequence vanishes, while we now get a number of changes in sign in each subsequence equal to the length of the subsequence minus 1. The total number of changes in sign is thus the equal to the length if the sequence minus the number of subsequences. The former is even and the latter is odd, therefore the total number of changes in sign in the sequence $(-1)^k c_k$ is odd.