Let f=0 be a polynomial with real coefficients. Define the sequence f0,f1,f2,… of polynomials by f0=f and fn+1=fn+fn′ for every n≥0. Prove that there exists a number N such that for every n≥N, all roots of fn are real.
Original from the official PDF
This transcription was compared symbol by symbol with the original, but not yet by a person.
Time on this problem
Work for at least 45 minutes before opening the solution.
Official solution
Solution. For the proof, we need the following
Lemma 1. For any polynomial g, denote by d(g) the minimum distance of any two of its real zeros (d(g)=∞ if g has at most one real zero). Assume that g and g+g′ both are of degree k≥2 and have k distinct real zeros. Then d(g+g′)≥d(g).
Proof of Lemma 1: Let x1<x2<⋯<xk be the roots of g. Suppose a,b are roots of g+g′ satisfying 0<b−a<d(g). Then, a,b cannot be roots of g, and
g(a)g′(a)=g(b)g′(b)=−1.(1)
Since gg′ is strictly decreasing between consecutive zeros of g, we must have a<xj<b for some j.
For all i=1,2,…,k−1 we have xi+1−xi>b−a, hence a−xi>b−xi+1. If i<j, both sides of this inequality are negative; if i≥j, both sides are positive. In any case, a−xi1<b−xi+11, and hence
Now we turn to the proof of the stated problem. Denote by m the degree of f. We will prove by induction on m that fn has m distinct real zeros for sufficiently large n. The cases m=0,1 are trivial; so we assume m≥2. Without loss of generality we can assume that f is monic. By induction, the result holds for f′, and by ignoring the first few terms we can assume that fn′ has m−1 distinct real zeros for all n. Let us denote these zeros by x1(n)>x2(n)>⋯>xm−1(n). Then fn has minima in x1(n),x3(n),x5(n),…, and maxima in x2(n),x4(n),x6(n),…. Note that in the interval (xi+1(n),xi(n)), the function fn+1′=fn′+fn′′ must have a zero (this follows by applying Rolle's theorem to the function exfn′(x)); the same is true for the interval (−∞,xm−1(n)). Hence, in each of these m−1 intervals, fn+1′ has exactly one zero. This shows that
Lemma 2. We have limn→∞fn(xj(n))=−∞ if j is odd, and n→∞limfn(xj(n))=+∞ if j is even.
Lemma 2 immediately implies the result: For sufficiently large n, the values of all maxima of fn are positive, and the values of all minima of fn are negative; this implies that fn has m distinct zeros.
Proof of Lemma 2: Let d=min{d(f′),1}; then by Lemma 1, d(fn′)≥d for all n. Define ε=mm−1(m−1)dm−1; we will show that
fn+1(xj(n+1))≥fn(xj(n))+εfor j even.(3)
(The corresponding result for odd j can be shown similarly.) Do to so, write f=fn, b=xj(n), and choose a satisfying d≤b−a≤1 such that f′ has no zero inside (a,b). Define ξ by the relation b−ξ=m1(b−a); then ξ∈(a,b). We show that f(ξ)+f′(ξ)≥f(b)+ε.
Together with (2) this shows (3). This finishes the proof of Lemma 2.
[Figure in the original PDF.]
Transcribed from the official solutions, pages 3–4. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.