Iranian Mathematical Olympiad

We prove this statement by induction. The base is clear, by the induction hypothesis assumes that
$$x^{n-1}|P(R_{n-1}(x)) - R_{n-1}(2x)$$
if it is also divisible by $x^n$ then we are done. Otherwise, set $R_n(x) = R_{n-1}(x) + a x^{n-1}$. Then $R_n(x) \equiv R_{n-1}(x) \pmod{x^{n-1}}$ and so we have
$$x^{n-1}|P(R_n(x)) - R_n(2x)$$
Assume that $P(x) = \sum a_j x^j$, $R_{n-1}(x) = \sum b_j x^j$, then the coefficient of $x^{n-1}$ in $P(R_n(x)) - R_n(2x)$ is equal to $a a_1 - 2^{n-1} a + f(a_2, \dots, a_n, b_j)$; we can set $a = \frac{-f}{a_1 - 2^{n-1}}$ unless $a_1 = 2^{n-1}$, so we have to show that this does not happen.
If we set $x = 0$ in the hypothesis we get $P(0) = 0$, and if we check the coefficient of $x$ in $P(Q(x)) - Q(2x)$ we get $a_1 b_1 - 2 b_1 = 0$ but we know that $b_1 \ne 0$ so we should have $a_1 = 2$ which means that $a_1 \ne 2^{n-1}$ for $n \ge 3$.
■