uniolympiads Ελληνικά

IMC 2007, Day 2, Problem 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.

Original from the official 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.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

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 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.]

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.

How did it go?