AustriaMO2011

Solution: We can, in fact, show that each of the expressions in the second sum is not greater than the corresponding expression in the first, multiplied by the factor $\frac{k}{k+1}$. Substituting $y:=x_j^{2k}$, this means that we wish to show $$\frac{1}{y^2+k+2}\le \frac{k}{k+1}\cdot \frac{1}{y+k}$$ Since $y$ is certainly positive for $k>0$, this is equivalent to $(k+1)(y+k)\le k(y^2+k+2)$, or $P(y)=k{y}^2-(k+1)y+k\ge 0$. This polynomial is quadratic in $y$, and we have $P(0)=k>0$. For the discriminant of the polynomial we have $$(k+1{)}^2-4k^2=-3k^2+2k+1\le -3k^2+3k=-3k(k-1)\le 0,$$ and we see that the polynomial can only assume positive values, which completes the proof. qed