Math Olympiad Second Stage Training Camp, 2015

It is easy to verify that the $\ge$ defined above satisfies the property that adding or subtracting the same polynomial on both sides preserves the relation.

(1). Suppose the conclusion does not hold, then we derive a contradiction below.

We now use induction on height to prove $a_i = b_i, \forall i = 1, 2, ..., n$.

First prove $a_n = b_n$: consider comparing the coefficient of $x^{n^2}$, the left side is $a_n^{n+1} + b_n^{n+1}$, the right side is $a_n^n b_n + a_n b_n^n$, left side $\ge$ right side with equality holding at $a_n = b_n$, but by assumption equality must hold.

Assume $a_i = b_i, \forall i = k, k + 1, ..., n$ holds, then the original expression can be written as
$$\begin{aligned} & a_n f(x)^n + a_{n-1} f(x)^{n-1} + \cdots + a_k f(x)^k \\ & \qquad + \cdots + a_0 + b_n g(x)^n + b_{n-1} g(x)^{n-1} + \cdots + b_k g(x)^k + \cdots + b_0 \\ \ge & a_n g(x)^n + a_{n-1} g(x)^{n-1} + \cdots + a_k g(x)^k \\ & + \cdots + a_0 + b_n f(x)^n + b_{n-1} f(x)^{n-1} + \cdots + b_k f(x)^k + \cdots + b_0 \end{aligned}$$
which is equivalent to
$$\begin{aligned} & a_{k-1} f(x)^{k-1} + \cdots + a_0 + b_{k-1} g(x)^{k-1} + \cdots + b_0 \\ \ge & a_{k-1} g(x)^{k-1} + \cdots + a_0 + b_{k-1} f(x)^{k-1} + \cdots + b_0 \end{aligned}$$
It is not hard to see that in the left and right expressions the coefficients of $x^q$ will be the same $\forall q > n(k-2)+k-1$ (because the coefficients are all chosen from $a_n$ to $a_k$), comparing the coefficient of the $x^{n(k-2)+k-1}$ term, the left side is $(k-1)a_n^{k-2}(a_{k-1}^2 + b_{k-1}^2)$, the right side is $(k-1)a_n^{k-2} \times 2a_{k-1}b_{k-1}$, by the AM-GM inequality the left side $\ge$ the right side with equality holding at $a_{k-1} = b_{k-1}$, but by assumption equality must hold.

By mathematical induction we obtain $f(x) = g(x)$, a contradiction!

(2). $f(x) \ge g(x)$ is equivalent to the existence of a sufficiently large $M$ such that $\forall m > M, f(m) \ge g(m)$. Without loss of generality, $f(x) \ge g(x)$; also, the original expression is equivalent to $(f-g)(f(x)) \ge (f-g)(g(x))$, and the leading coefficient of $f-g$ is positive, so there exists a sufficiently large $M$ such that $\forall m > M$: (i) $(f-g)(m)$ is increasing, (ii) $f(m) \ge g(m)$, then $(f-g)(f(m)) \ge (f-g)(g(m))$, hence the result is proved.