Unknown

5.2. Tests for Real Zeros 175

by induction on the degree of the polynomials. Suppose it holds for all de-

grees less than n = degp(t). To avoid complications, let us suppose that

the derivative does not vanish at either u or v.

There are a number of cases to consider:

(1) p and p’ have the same sign at u and the same sign at v;

(2) p and p’ have the same sign at u and opposite signs at v;

(3) p and p’ have opposite signs at u and the same sign at v;

(4) p and p’ have opposite signs at both u and v.

A second subdivision of cases is whether p has at least one or no zeros in

the interval [u, v].

Suppose, to take a special case, that p does have at least one zero in the

interval, the smallest being y and the largest .z, so that u < y 5 z < v, and

that p and p’ have the same sign at u but opposite signs at v. Assigning

A and B the meanings of Exercise 2.17 and C and D the corresponding

meaning for p’, establish the following (generous use of graph-sketching is

recommended):

(i) A=C,B=D+l;

(ii) If p(t) has k zeros counting multiplicity in [u, v], then p’ has k - 1 + 2i

zeros in [y, ~1 for some nonnegative integer i;

(iii) p’ has an odd number of zeros between u and y;

(iv) p’ has an odd number of zeros between z and v.

Now use the induction hypothesis that the number of zeros of p’ is less
than C - D by an even nonnegative integer.

E.48. Sturm’s Theorem. The difficulty with the Method of Fourier-
Budan is that, while the polynomials p(t) and p(t) + c might have different
numbers of real roots in an interval, the taking of the derivative suppresses
the constant c and causes information to be lost. A more refined method,
due to Sturm, permits us to actually count the number of real roots in any
interval, although Sturm’s sequences are more troublesome to obtain than
Fourier-Budan sequences.
Let p(t) be a given real polynomial. To define the polynomial sequence
(PO(t), Pl(t),P2(t>l .) we need, we make a continued use of the division
algorithm in much the same way as is done for the Euclidean algorithm.
The pi(t) are chosen to satisfy:

POW = P(t)

pi(t) = p’(t), the derivative of p(t)