# 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?

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)$$
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.