# Given nonnegative $x_1, \cdots, x_n \geq 0$, show that $x_1 + \cdots + x_n \geq \sqrt{1} + \sqrt{3} + \cdots + \sqrt{2n-1}$

Let $x_1, \cdots, x_n \geq 0$ be real nonnegative numbers satisfying $x_1 \leq x_2 \leq \cdots \leq x_n$. For all integer $1 \leq m \leq n$, let

$$x_1^2 + \cdots + x_m^2 \geq m^2.$$

Show that $x_1 + \cdots + x_n \geq \sqrt{1} + \sqrt{3} + \cdots \sqrt{2n-1}$.

My intuition says that the best way to solve this problem will use QM-AM-GM, but I haven't been able to find anything. I did notice that the equality case occurs when $x_1 = \sqrt{1}$, $x_2 = \sqrt{3}$, ..., $x_n = \sqrt{2n-1}$. This follows from the formula $1 + 3 + 5 + \cdots + (2n-1) = n^2$.

Also, I was thinking that it could be easier to prove the slightly stronger hypothesis $x_1 + \cdots + x_m \geq \sqrt{1} + \sqrt{3} + \cdots + \sqrt{2m-1}$ by induction, but I haven't been able to get any results with this idea either.

Can anybody give me hints to point me in the right direction for solving this problem?

Hints:
1. Argue it is enough to consider the cases with $\displaystyle \sum_1^n x_i^2 = n^2$.
2. Use Karamata's inequality with the concave function $t \mapsto \sqrt{t}$, after observing that $$(x_1^2, x_2^2, x_3^2, \dots x_n^2) \prec (1, 3, 5, \dots 2n-1)$$

• This is a nice and simple solution, but it feels like using Karmata is like nuking a mosquito. Do you think there is a more elementary proof?
– aras
Dec 1, 2016 at 11:54
• @aras another argument using the linear objective function and convex domains comes easily to mind, though not any argument with QM-AM-GM or something like that. Have to go now though, will get back later if something along more basic inequalities strikes. Dec 1, 2016 at 11:58
• OK, thanks anyway.
– aras
Dec 1, 2016 at 12:01

Here is another way. The constraints (after some work), boil down to $x_1\in [1, x_2], x_2\in [\max(\sqrt3, x_1), x_3], x_3\in[\max(\sqrt5, x_2), x_4], \dots x_n \in [\max(\sqrt{2n-1},x_{n-1}), \infty)$

Clearly the linear function gets minimised when the variables take the lower boundaries of their respective intervals. So we have the minimum when $x_i=\sqrt{2i-1}$ and the inequality is done.