Given a monic quadratic polynomial $Q(x)$, define \[ Q_n (x) = \underbrace{Q(Q(\cdots(Q(x))\cdots))}_{\text{compose $n$ times}} \]for every natural number $n$. Let $a_n$ be the minimum value of the polynomial $Q_n(x)$ for every natural number $n$. It is known that $a_n > 0$ for every natural number $n$ and there exists some natural number $k$ such that $a_k \neq a_{k+1}$. (a) Prove that $a_n < a_{n+1}$ for every natural number $n$. (b) Is it possible to satisfy $a_n < 2021$ for every natural number $n$? Proposed by Fajar Yuliawan
Problem
Source: Indonesian Stage 1 TST for IMO 2022, Test 1 (Algebra)
Tags: algebra, polynomial, inequalities
mihaig
12.12.2021 09:56
Nice one. Who is the author?
cadaeibf
12.12.2021 12:10
We do this more generally for a strictly convex twice differentiable function $f$ with a single minimum in $x_0$. We classify $3$ possible behaviours for $a_n$. $I$)$f(x)>x$ $\forall x\in\mathbb{R}$. Therefore we have $t=inf(im(f(x)-x))=min(im(f(x)-x))>0$, or in other words $f(x)\geq x+t$ $\forall x\in \mathbb{R}$. In this case $f_{n+1}(x)\geq f_n(x)+t\geq a_n+t$, which implies $a_{n+1}\geq a_n+t$, and thus $a_n$ is a strictly increasing unbounded sequence. $II$) $f(x)$ has two points of intersection $x_1< x_2$ and $x_1\leq x_0<x_2$. Considering the function $f_n$, we have $f_n(x_2)=2$ and $f_n(x_1)=x_1$, and so by intermediate value theorem there is a $c$ such that $f_n(c)=x_0$, and thus $f_{n+1}(x)= f(f_n(x))\geq f(x_0)=a_1$, and so $a_n$ is constant. $III$) $f(x)$ has two points (they may be coincident, which couldn't happen before) $x_1\leq x_2$, and $x_0<x_1$. For $x<x_1$ we have $f(x)>x$. Since $f_n'=f'(f_{n-1})\cdots f'(x)$, to achieve minimum we must have $f'(f_{k}(x))=0$ for some $k\geq 0$ which implies $f_k(x)=x_0$. However if $k>0$ we have $f_k(x)\geq f(x_0)>x_0$, and so the only minimum is always in $x_0$. Now we note by induction that, since $f$ is increasing in $[x_0,x_1]$ and since $f(x)>x$ $\forall x\in [x_0,x_1)$, $x_1=f_{n+1}(x_1)>f_{n+1}(x_0)>f_n(x_0)=a_n>a_{n-1}>\cdots >a_1>x_0$, and this $a_n$ is a strictly increasing bounded function, which by monotone convergence theorem must converge, and it must in fact converge to $x_1$. Now we finally return to our problem: We couldn't have case $I$ since $a_n$ is constant. In both cases $II$ and $III$ part a) was proved. For part b) it suffices to take a function which satisfies the hypothesis $x_0<x_1\leq x_2$. For example, $Q(x)=(x-\frac{1}{4})^2+0.01$ works since $a_1>0$ and $x_1<2021$.
somebodyyouusedtoknow
15.12.2021 18:09
(a)Let $Q(a) = a_1$, then $Q(x) = (x - a)^2 + a_1$.
Claim 1: $a_1 > a$
Proof. Suppose (FTSOC) $a \geq a_1$. Notice that $Q_1(a) = a_1$. Assume that $Q_n(b_n) = a_1$ where $b_n \geq a$ for some $n \geq 1$. Let $b_{n+1} = a + \sqrt{b_n - a_1} \geq a$, hence $Q(b_{n+1}) = b_n$ and
\[ Q_{n+1} (b_{n+1}) = Q_n (Q(b_{n+1})) = Q_n(b_n) = a_1. \]Since $Q_n(x) \geq a_1$ for every natural number $n$, we obtain that $a_n = a_1$ for all $n$, a contradiction!
Claim 2: $a_n = Q_n(a)$
Proof. For $n=1$ it's true since $a_1 = Q_1(a)$. Assume that $a_n = Q_n(a)$ for some $n \geq 1$. Thus, $Q_n(x) \geq Q_n(a) \geq a_1 > a$, so
\[ Q_{n+1} (x) = Q(Q_n(x)) = (Q_n(x) - a)^2 + a_1 \geq (Q_n(a) - a)^2 + a_1 = Q_{n+1} (a). \]So $a_{n+1} = Q_{n+1} (a)$. Claim 2 is proven by induction.
Claim 3: $a_{n+1} > a_n$ for every natural number $n$.
Proof. Since $a_1 > a$, then
\[ a_2 = Q_2(a) = Q(a_1) = (a_1 - a)^2 + a_1 > a_1 > a. \]Suppose it holds that $a_{n+1} > a_n > a$ for some natural number $n$, then
\[ a_{n+2} = Q(a_{n+1}) = (a_{n+1} - a)^2 + a_1 > (a_n - a)^2 + a_1 = a_{n+1} > a. \]So claim 3 is proven by induction. $\blacksquare$
(b)It is possible. Take $Q_1(x) = x^2 + \frac{1}{4}$. Notice that $a_1 = \frac{1}{4}$ and
\[ a_{n+1} = Q_{n+1} (0) = Q(Q_n(0)) = Q(a_n) = a_n^2 + \frac{1}{4}. \]Claim. $a_n < \frac{1}{2}$ for every $n \geq 1$.
Proof. It obviously holds for $n = 1$. If $a_n < \frac{1}{2}$, then
\[ a_{n+1} = a_n^2 + \frac{1}{4} < \frac{1}{4} + \frac{1}{4} = \frac{1}{2}. \]So the claim is proven by induction. $\blacksquare$
Translated by yours truly, from Indonesian.
lazizbek42
30.03.2022 07:39
This example very nice for part (b) $$x^2+\frac{1}{4}x+\frac{1}{8}$$