AustriaMO

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) = ky^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