From: Kurt Foster Subject: Re: Descartes' rule of signs Date: 18 Jun 1999 15:49:32 GMT Newsgroups: sci.math In <7kc9tf$4v1$1@nnrp1.deja.com>, jvoight34@my-deja.com said: . Does anyone know of a proof of Descartes' rule of signs, i.e. the . number of positive real solutions to a polynomial is a multiple of two . less than the number of sign changes in the coefficients? Here is a fairly simple proof for polynomials that are not identically zero. The result is trivial for nonzero constant polynomials (no zeros, no sign variations). It obviously suffices to consider monic polynomials f(x) = x^n + a_(n-1) * x^(n-1) + ... + a_1 * x + a_0, where n is a positive integer and a_0 is not equal to zero. Clearly, there are evenly many sign variations when a_0 > 0, and oddly many when a_0 < 0. Now if r is a zero of f(x), we have f(x) = (x - r) * g(x) where g(x) is monic, with nonzero constant term -a_0/r, which is of opposite sign to a_0 if r > 0. So the number of sign variations of g(x) differs from that of f(x) by an odd number when r > 0. Now let f(x) = PRODUCT, i = 1 to k, (x - r_i) * h(x), where the r_i are all positive. Then the number of sign variations of h(x) differs from that of f(x) by the sum of k odd numbers. So the number of sign variations of f(x) differs from that of h(x) by an odd number if k is odd, and by an even number if k is even. To complete the proof, we show that if a monic polynomial with nonzero constant term has no positive zeros, then the constant term is positive - that is, the polynomial must have an even number of sign variations. This is trivial when the polynomial is constantly 1. We assume a nonconstant monic polynomial, and note that the constant term is the polynomial's value at x = 0. Now let x increase, starting from 0. Because the polynomial is monic, it will take positive values when x is very large. Because it has no positive zeros, it cannot change sign when x is positive. Therefore, its constant term must be positive also. ============================================================================== From: Kurt Foster Subject: Re: Descartes' rule of signs Date: 25 Jun 1999 17:16:25 GMT Newsgroups: sci.math In <7kp27l$1enc@r02n01.cac.psu.edu>, William C Waterhouse said: . In article <7kdpqc$6rs$1@news1.rmi.net>, . Kurt Foster writes: .. In <7kc9tf$4v1$1@nnrp1.deja.com>, jvoight34@my-deja.com said: ... Does anyone know of a proof of Descartes' rule of signs, i.e. the ... number of positive real solutions to a polynomial is a multiple of two ... less than the number of sign changes in the coefficients? .. Here is a fairly simple proof ... [whack] . So far as I can see, this is only a partial proof. It shows that . the numbers differ by a multiple of two, but it does not seem . to show that the number of positive solutions is less than or . equal to the number of sign changes. You're right - I failed to prove that the number of sign changes doesn't go UP when you divide a monic polynomial f(x) by a factor x-r, r a positive zero. I merely showed that it changes by an odd number. To show that the quotient can't have any more sign changes than the dividend, again let f(x) = x^n + a_(n-1) * x^(n-1) + ... + a_1 * x + a_0, where n is a positive integer and a_0 is not equal to zero. Let r be a zero of f, and f(x) = (x - r) * g(x), with g(x) = x^(n-1) + b_(n-2) * x^(n-2) + ... + b_1 * x + b_0. Then b_(n-1) = 1, -r*b_(n-k) + b_(n-k-1) = a_(n-k) for k = 1 to n-1, which may be rewritten b_(n-k-1) = r*b_(n-k) + a_(n-k), k = 1 to n-1 -r*b_0 = a_0. Now the rewritten relation shows that if r > 0, then as you work down from the highest-degree terms, the first sign change in the b's cannot occur until there is a sign change in the a's - perhaps not even then. And no subsequent change in sign of the b's can occur before another change in sign in the a's. So when r > 0, the quotient g(x) cannot have any more sign changes than the dividend f(x). ============================================================================== From: stew.sep.stanford.edu@forum.swarthmore.edu (Stewart A. Levin , @) Subject: Re: Descartes' Rule of signs Date: 20 Sep 1999 16:08:31 -0400 Newsgroups: sci.math There are two proofs on my web page http://sepwww.stanford.edu/oldsep/stew/ One is due to Gauss, the other Laguerre. Both are "classics" - Stew