uniolympiads English

IMC 2007, Ημέρα 2, Θέμα 6

Let f≠0f \ne 0 be a polynomial with real coefficients. Define the sequence f0,f1,f2,…f_0, f_1, f_2, \dots of polynomials by f0=ff_0 = f and fn+1=fn+fn′f_{n+1} = f_n + f_n' for every n≥0n \ge 0. Prove that there exists a number NN such that for every n≥Nn \ge N, all roots of fnf_n are real.

Πρωτότυπο από το επίσημο PDFLet f 6 = 0 be a polynomial with real coefficients. Define the sequence f 0 , f 1 , f 2 , . . . of polynomials by f 0 = f and f n+1 = f n + f n ′ for every n ≥ 0. Prove that there exists a number N such that for every n ≥ N, all roots of f n are real.

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

Solution. For the proof, we need the following

Lemma 1. For any polynomial gg, denote by d(g)d(g) the minimum distance of any two of its real zeros (d(g)=∞d(g)=\infty if gg has at most one real zero). Assume that gg and g+g′g+g' both are of degree k≥2k\ge2 and have kk distinct real zeros. Then d(g+g′)≥d(g)d(g+g')\ge d(g).

Proof of Lemma 1: Let x1<x2<⋯<xkx_1<x_2<\dots<x_k be the roots of gg. Suppose a,ba,b are roots of g+g′g+g' satisfying 0<b−a<d(g)0<b-a<d(g). Then, a,ba,b cannot be roots of gg, and

g′(a)g(a)=g′(b)g(b)=−1.(1)\frac{g'(a)}{g(a)}=\frac{g'(b)}{g(b)}=-1. \tag{1}
Since g′g\frac{g'}{g} is strictly decreasing between consecutive zeros of gg, we must have a<xj<ba<x_j<b for some jj.

For all i=1,2,…,k−1i=1,2,\dots,k-1 we have xi+1−xi>b−ax_{i+1}-x_i>b-a, hence a−xi>b−xi+1a-x_i>b-x_{i+1}. If i<ji<j, both sides of this inequality are negative; if i≥ji\ge j, both sides are positive. In any case, 1a−xi<1b−xi+1\frac1{a-x_i}<\frac1{b-x_{i+1}}, and hence

g′(a)g(a)=∑i=1k−11a−xi+1a−xk⏟<0<∑i=1k−11b−xi+1+1b−x1⏟>0=g′(b)g(b)\frac{g'(a)}{g(a)}=\sum_{i=1}^{k-1}\frac1{a-x_i}+\underbrace{\frac1{a-x_k}}_{<0}<\sum_{i=1}^{k-1}\frac1{b-x_{i+1}}+\underbrace{\frac1{b-x_1}}_{>0}=\frac{g'(b)}{g(b)}
This contradicts (1).

Now we turn to the proof of the stated problem. Denote by mm the degree of ff. We will prove by induction on mm that fnf_n has mm distinct real zeros for sufficiently large nn. The cases m=0,1m=0,1 are trivial; so we assume m≥2m\ge2. Without loss of generality we can assume that ff is monic. By induction, the result holds for f′f', and by ignoring the first few terms we can assume that fn′f_n' has m−1m-1 distinct real zeros for all nn. Let us denote these zeros by x1(n)>x2(n)>⋯>xm−1(n)x_1^{(n)}>x_2^{(n)}>\dots>x_{m-1}^{(n)}. Then fnf_n has minima in x1(n),x3(n),x5(n),…x_1^{(n)},x_3^{(n)},x_5^{(n)},\dots, and maxima in x2(n),x4(n),x6(n),…x_2^{(n)},x_4^{(n)},x_6^{(n)},\dots. Note that in the interval (xi+1(n),xi(n))(x_{i+1}^{(n)},x_i^{(n)}), the function fn+1′=fn′+fn′′f_{n+1}'=f_n'+f_n'' must have a zero (this follows by applying Rolle's theorem to the function exfn′(x)e^xf_n'(x)); the same is true for the interval (−∞,xm−1(n))(-\infty,x_{m-1}^{(n)}). Hence, in each of these m−1m-1 intervals, fn+1′f_{n+1}' has exactly one zero. This shows that

x1(n)>x1(n+1)>x2(n)>x2(n+1)>x3(n)>x3(n+1)>…(2)x_1^{(n)}>x_1^{(n+1)}>x_2^{(n)}>x_2^{(n+1)}>x_3^{(n)}>x_3^{(n+1)}>\ldots \tag{2}

Lemma 2. We have lim⁡n→∞fn(xj(n))=−∞\lim_{n\to\infty}f_n(x_j^{(n)})=-\infty if jj is odd, and lim⁡n→∞fn(xj(n))=+∞\lim\limits_{n\to\infty}f_n(x_j^{(n)})=+\infty if jj is even.

Lemma 2 immediately implies the result: For sufficiently large nn, the values of all maxima of fnf_n are positive, and the values of all minima of fnf_n are negative; this implies that fnf_n has mm distinct zeros.

Proof of Lemma 2: Let d=min⁡{d(f′),1}d=\min\{d(f'),1\}; then by Lemma 1, d(fn′)≥dd(f_n')\ge d for all nn. Define ε=(m−1)dm−1mm−1\varepsilon=\dfrac{(m-1)d^{m-1}}{m^{m-1}}; we will show that

fn+1(xj(n+1))≥fn(xj(n))+εfor j even.(3)f_{n+1}(x_j^{(n+1)})\ge f_n(x_j^{(n)})+\varepsilon\quad\text{for }j\text{ even}. \tag{3}
(The corresponding result for odd jj can be shown similarly.) Do to so, write f=fnf=f_n, b=xj(n)b=x_j^{(n)}, and choose aa satisfying d≤b−a≤1d\le b-a\le1 such that f′f' has no zero inside (a,b)(a,b). Define ξ\xi by the relation b−ξ=1m(b−a)b-\xi=\dfrac1m(b-a); then ξ∈(a,b)\xi\in(a,b). We show that f(ξ)+f′(ξ)≥f(b)+εf(\xi)+f'(\xi)\ge f(b)+\varepsilon.

Notice, that

f′′(ξ)f′(ξ)=∑i=1m−11ξ−xi(n)=∑i<j1ξ−xi(n)⏟<1ξ−a+1ξ−b+∑i>j1ξ−xi(n)⏟<0<(m−1)1ξ−a+1ξ−b=0.\begin{aligned}\frac{f''(\xi)}{f'(\xi)}&=\sum_{i=1}^{m-1}\frac1{\xi-x_i^{(n)}}\\&=\sum_{i<j}\underbrace{\frac1{\xi-x_i^{(n)}}}_{<\frac1{\xi-a}}+\frac1{\xi-b}+\sum_{i>j}\underbrace{\frac1{\xi-x_i^{(n)}}}_{<0}\\&<(m-1)\frac1{\xi-a}+\frac1{\xi-b}=0.\end{aligned}
The last equality holds by definition of ξ\xi. Since f′f' is positive and f′′f′\dfrac{f''}{f'} is decreasing in (a,b)(a,b), we have that f′′f'' is negative on (ξ,b)(\xi,b). Therefore,
f(b)−f(ξ)=∫ξbf′(t)dt≤∫ξbf′(ξ)dt=(b−ξ)f′(ξ)f(b)-f(\xi)=\int_\xi^bf'(t)dt\le\int_\xi^bf'(\xi)dt=(b-\xi)f'(\xi)
Hence,
f(ξ)+f′(ξ)≥f(b)−(b−ξ)f′(ξ)+f′(ξ)=f(b)+(1−(ξ−b))f′(ξ)=f(b)+(1−1m(b−a))f′(ξ)≥f(b)+(1−1m)f′(ξ).\begin{aligned}f(\xi)+f'(\xi)&\ge f(b)-(b-\xi)f'(\xi)+f'(\xi)\\&=f(b)+(1-(\xi-b))f'(\xi)\\&=f(b)+(1-\tfrac1m(b-a))f'(\xi)\\&\ge f(b)+(1-\tfrac1m)f'(\xi).\end{aligned}
Together with
f′(ξ)=∣f′(ξ)∣=m∏i=1m−1∣ξ−xi(n)∣⏟≥∣ξ−b∣≥m∣ξ−b∣m−1≥dm−1mm−2f'(\xi)=|f'(\xi)|=m\prod_{i=1}^{m-1}\underbrace{|\xi-x_i^{(n)}|}_{\ge|\xi-b|}\ge m|\xi-b|^{m-1}\ge\frac{d^{m-1}}{m^{m-2}}
we get
f(ξ)+f′(ξ)≥f(b)+ε.f(\xi)+f'(\xi)\ge f(b)+\varepsilon.
Together with (2) this shows (3). This finishes the proof of Lemma 2.

[Figure in the original PDF.]

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 3–4. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;