WakeUp wrote: Let $f_1(x)$ be a polynomial of degree $2$ with the leading coefficient positive and $f_{n+1}(x) =f_1(f_n(x))$ for $n\ge 1.$ Prove that if the equation $f_2(x)=0$ has four different non-positive real roots, then for arbitrary $n$ then $f_n(x)$ has $2n$ different real roots. Are you sure about the text ? I understand that $f_n(x)$ has exactly $2n$ different real roots. But maybe you want to say that $f_n(x)$ has at least $2n$ different real roots. If you mean "exactly", I think it's wrong : Choose $f_1(x)=10x^2+30x+20$ and $f_3(x)$ has exactly $8$ different real roots and not $6$.

Sorry, it should've been $2^n$ rather than $2n$.. pco wrote: Are you sure about the text ? To be honest, no! The problems were translated into English that was very difficult to understand..

$f_2(x)=0 \Leftrightarrow f_1(x)=r_i$ where $f_1(r_i)=0$. So If $f_2$ has four distinct real roots then $f_1$ has two distinct real roots, say $r_1>r_2$. Step 1: $\min\{f_1\} < r_2 < r_1 \le 0$ Suppose $r_1 > 0$, then since $f_1(r_1)=0$ and $f_1(+\infty)=+\infty$ then by continuity of $f_1$ there exists $u > r_1$ such that $f_1(u)=r_1$. But this implies that $f_2(u)=0$, contradicting the fact that $f_2$ has non-positive roots. So $r_2 < r_1 \le 0$. Since $f_1(x)=r_2$ has real distinct solutions we need $r_2 \ge \min\{f_1\}$. If $r_2 = \min\{f_1\}$ then $f_2$ would have a double root, contradicting the fact that $f_2$ has distinct roots. So $r_2 > \min\{f_1\}$ Step 2: Let $R_1 = \{r_1,r_2\}$, and define $R_n = \{r \, : \, f_1(r)\in R_{n-1}\}$. This means that $R_n$ is the solution set to $f_n(x)=0$. Now for $k\ge 2$ we can show by induction that $r_2 \le \min\{R_k\} < \max\{R_k\} \le r_1$. Because if $R_{k-1}$ contains only non-negative entries then solutions to $f_1(r) \in R_k$ imply $f_1(r) \le 0$, but $f_1$ is only non-positive between $r_1$ and $r_2$, and the conclusion follows. Now we show by induction that $|R_n| = 2^n$. The base case for $n=1,2$ are given so assume true for $n=k$ and consider case $n=k+1$. Since we have shown that all elements of $R_{k}$ are between $r_1$ and $r_2$, we know that any elements $r_i \in R_k$ admits exactly two solutions $f_1(x)=r_i$. Since $f_1$ is many-to-one and not many-to-many, the two solutions to $f(x)=r_i$ are unique for all $r_i$ meaning that $|R_{k+1}| = 2|R_k|$. So the inductive step is complete $\square$

Assume that $f_1(x)=ax^2+bx+c=a(x-x_1)(x-x_2), a>0, x_1>x_2$, $f_2(x)=0 \leftrightarrow f_1(x)=x_1$ or $f_1(x)=x_2$. $f_1(x)=x_1 \leftrightarrow ax^2+bx+c-x_1=0$, this equation has 2 distinct non-positive roots $\implies b\geq 0, c\geq x_1>x_2$.Suppose $x_1>0,x_2<0 \implies c<0<x_1(><)\implies 0\geq x_1>x_2\implies c\geq 0$.Now we will prove $f_n(x)$ has $2^n$ roots $\leq 0$ by induction on $n$.For $n=1$, done. Assume this is true for $n$, we will prove it is true for $n+1$. Indeed, we have $f_n(x)=a(x-r_1)(x-r_2)...(x-r_{2^n}), f_{n+1}(x)=f_n(f_1(x))=0 \leftrightarrow f_1(x)=r_i, i=1,2...,2^n \leftrightarrow g_i(x)=ax^2+bx+c-r_i=0$. We have $\Delta_i = b^2-4a(c-r_i)>b^2-4a(c-x_2) \geq 0, i=1,2,..,2^n$ and $S_i=\frac{-b}{a} \geq 0, P_i=\frac{c-r_i}{a} \geq 0 \implies g_i(x)$ has 2 distinct non-positive roots or $f_{n+1}(x)$ has $2^{n+1}$ non-positive roots.

very nice problem . has a deep adventure inside it . which we dont see much in problems. enjoyed solving it!