Karamata again... Define a sequence $\left(b_n\right)_{n\in\mathbb{N}}$ by $b_k=\sqrt{k}-\sqrt{k-1}$ for every k. Since $b_k=\sqrt{k}-\sqrt{k-1}=\frac{\left(\sqrt{k}+\sqrt{k-1}\right)\left(\sqrt{k}-\sqrt{k-1}\right)}{\sqrt{k}+\sqrt{k-1}}$ $=\frac{k-\left(k-1\right)}{\sqrt{k}+\sqrt{k-1}}=\frac{1}{\sqrt{k}+\sqrt{k-1}}$, it is clear that this sequence $\left(b_n\right)$ is decreasing (since, when k increases, both $\sqrt{k}$ and $\sqrt{k-1}$ increase, so that $\sqrt{k}+\sqrt{k-1}$ increases, and thus $b_k=\frac{1}{\sqrt{k}+\sqrt{k-1}}$ decreases). Hence, for every index k with $1\leq k\leq n$, the numbers $b_1$, $b_2$, ..., $b_k$ are the k greatest numbers among the n numbers $b_1$, $b_2$, ..., $b_n$. Hence, the sum $\sum_{j=1}^k b_j$ is the sum of the k greatest numbers among the n numbers $b_1$, $b_2$, ..., $b_n$. Since $\sum_{j=1}^k b_j=\sum_{j=1}^k\left(\sqrt{j}-\sqrt{j-1}\right)=\sqrt{k}-\sqrt{0}=\sqrt{k}$, we thus can state: The sum of the k greatest numbers among the n numbers $b_1$, $b_2$, ..., $b_n$ is $\sqrt{k}$. For the numbers $a_1$, $a_2$, ..., $a_n$, we don't know how they are arranged, and we can only say that the sum of the k greatest numbers among the n numbers $a_1$, $a_2$, ..., $a_n$ is greater or equal to the sum $\sum_{j=1}^k a_j$ (in fact, this is obvious: the sum of the k greatest numbers is greater or equal to the sum of just some k numbers). So altogether, for every index k with $1\leq k\leq n$, we have: - The sum of the k greatest numbers among the n numbers $a_1$, $a_2$, ..., $a_n$ is greater or equal to the sum $\sum_{j=1}^k a_j$. - By the condition of the problem, $\sum_{j=1}^k a_j \geq \sqrt{k}$. - The number $\sqrt{k}$ is the sum of the k greatest numbers among the n numbers $b_1$, $b_2$, ..., $b_n$. Combining this, we see that for every index k with $1\leq k\leq n$, the sum of the k greatest numbers among the n numbers $a_1$, $a_2$, ..., $a_n$ is greater or equal to the sum of the k greatest numbers among the n numbers $b_1$, $b_2$, ..., $b_n$. Now, we have the following fact: Karamata theorem for "pseudo-majorizing" number arrays: Let $a_1$, $a_2$, ..., $a_n$, $b_1$, $b_2$, ..., $b_n$ be 2n numbers from an interval $\mathcal{I}$ such that for every index k with $1\leq k\leq n$, the sum of the k greatest numbers among the n numbers $a_1$, $a_2$, ..., $a_n$ is greater or equal to the sum of the k greatest numbers among the n numbers $b_1$, $b_2$, ..., $b_n$ (but we don't require equality for k = n, i. e. we don't necessarily have $a_1+a_2+...+a_n=b_1+b_2+...+b_n$, but we only need $a_1+a_2+...+a_n\geq b_1+b_2+...+b_n$). Also, let f be a function which is convex and monotonically increasing on the interval $\mathcal{I}$. Then, $\sum_{j=1}^n f\left(a_j\right)\geq\sum_{j=1}^n f\left(b_j\right)$. This theorem can be easily deduced from the actual Karamata theorem. Now, applying this theorem to our numbers $a_1$, $a_2$, ..., $a_n$, $b_1$, $b_2$, ..., $b_n$, with the interval $\mathcal{I}=\mathbb{R}^+$ and the function $f\left(t\right)=t^2$ which is convex and monotonically increasing on $\mathbb{R}^+$, we get $\sum_{j=1}^n a_j^2\geq\sum_{j=1}^n b_j^2=\sum_{j=1}^n\left(\frac{1}{\sqrt{j}+\sqrt{j-1}}\right)^2>\sum_{j=1}^n\left(\frac{1}{\sqrt{j}+\sqrt{j}}\right)^2=\sum_{j=1}^n\left(\frac{1}{2\sqrt{j}}\right)^2$ $=\sum_{j=1}^n\frac{1}{4j}=\frac14\sum_{j=1}^n\frac{1}{j}$, and the problem is solved. EDIT: I just saw the same problem in a slightly different version being posted at http://www.artofproblemsolving.com/Forum/viewtopic.php?t=21262 . Darij

Darij, it's not Karamata's inequality. Actually this is called Hardy-Littlewood-Polya inequality.

cezar lupu wrote: Darij, it's not Karamata's inequality. Actually this is called Hardy-Littlewood-Polya inequality. Both names are okay. But even if the name is wrong, who cares?

Let us assume that $a_1 \ge a_2 \ge a_3.....\ge a_n$ .Also let $f_n(x): \mathbb{R^+}->\mathbb{R^+}$ such that $f_n(x)=\frac{1}{\sqrt{x_n}}$ Let try to prove $2\sum_{i=1}^{n}a_i^2$ $\ge \sum_{i=1}^{i=n}a_if(x)_i$ Now using Abel's inequality $\sum_{i=1}^{i=n}a_i(2a_i - f_i(x)) =$ (a_1 - a_2 )( 2a_1 - f_1(x) ) + (a_2 - a_3)(2a_1 + 2a_2 - $f_1(x) - f_2(x) ) + ..... ..+ (a_{n-1}$ $- a_{n} )(2\sum_{i=1}^{n-1}a_i -$ $\sum_{i=1}^{n-1} f_i(x) ) + x_n( 2\sum_{i=1}^{i=n} a_i - \sum_{i=1}^{n}f_i(x) )$ Need to prove that $2\sum_{i=1}^{k}a_i \ge \sum_{i=1}^{k}f_i(x)$ This means we need to show $\sum_{i=1}^{k}\frac{1}{\sqrt{x}}$ $\le 2\sqrt{k}$ That's very easy to show.

opptoinfinity wrote: Let us assume that $a_1 \ge a_2 \ge a_3.....\ge a_n$ .Also let $f_n(x): \mathbb{R^+}->\mathbb{R^+}$ such that $f_n(x)=\frac{1}{\sqrt{x_n}}$ Let try to prove $2\sum_{i=1}^{n}a_i^2$ $\ge \sum_{i=1}^{i=n}a_if(x)_i$ Now using Abel's inequality $\sum_{i=1}^{i=n}a_i(2a_i - f_i(x)) =$ (a_1 - a_2 )( 2a_1 - f_1(x) ) + (a_2 - a_3)(2a_1 + 2a_2 - $f_1(x) - f_2(x) ) + ..... ..+ (a_{n-1}$ $- a_{n} )(2\sum_{i=1}^{n-1}a_i -$ . $\sum_{i=1}^{n-1} f_i(x) ) + x_n( 2\sum_{i=1}^{i=n} a_i - \sum_{i=1}^{n}f_i(x) )$ Need to prove that $2\sum_{i=1}^{k}a_i \ge \sum_{i=1}^{k}f_i(x)$ This means we need to show $\sum_{i=1}^{k}\frac{1}{\sqrt{x}} \le 2\sqrt{k}$ That's very easy to show.

we proceed by Abel : denonte $b_{k} = \frac{1}{\sqrt{k}}$ note that our inequation to prove becomes : $$\sum_{i=1}^{n} 4{(x_{i})}^{2} \ge \sum_{i=1}^{n} {(b_{i})}^{2}$$ then we get that $$\sum_{i=1}^{n} 4{(x_{i})}^{2} - {(b_{i})}^{2} \ge {0}$$ and then we get $$\sum_{i=1}^{n} (2x_{i}+b_{i})(2x_{i}-b_{i}) \ge {0}$$ but we have $\sum_{i=1}^{n} (2x_{i}+b_{i}) \ge {0}$ then we only need to prove that $$\sum_{i=1}^{n} (2x_{i}-b_{i}) \ge {0}$$ note that $\sum_{i=1}^{n} (2x_{i}-b_{i}) =\sum_{i=1}^{n} (b_{i})(\frac{2x_{i}}{b_{i}} - 1) = \sum_{i=1}^{n} (X_{i})(b_{i}-b_{i+1})$ and $X_{i} = \sum_{j=1}^{i} \frac{2x_{i}}{b_{i}} - i$ .... note that $b_{i}>{b_{i+1}}$ thus we need to prove that $\sum_{i=1}^{n} X_{i} \ge {0}$ now bby AM GM we have $\sum_{j=1}^{i} \frac{x_{i}}{b_{i}} \ge {i{(\frac{x1*x2....xI}{b1*b2*b3...bI})}^{\frac{1}{i}}}$ which makes $\sum_{i=1}^{n} X_{i} \ge {0}$ finally we have $$\sum_{i=1}^{n} (2x_{i}-b_{i})=\sum_{i=1}^{n} (b_{i})(\frac{2x_{i}}{b_{i}} - 1) = \sum_{i=1}^{n} (X_{i})(b_{i}-b_{i+1}) \ge {0}$$

MithsApprentice wrote: Let $\, a_1, a_2, a_3, \ldots \,$ be a sequence of positive real numbers satisfying $\, \sum_{j=1}^n a_j \geq \sqrt{n} \,$ for all $\, n \geq 1$. Prove that, for all $\, n \geq 1, \,$ $$\sum_{j=1}^n a_j^2 > \frac{1}{4} \left( 1 + \frac{1}{2} + \cdots + \frac{1}{n} \right).$$ Using Cauchy-Bunyakovsky-Schwarz inequality, we have $$\sum_{j=1}^n a_j^2 \sum_{j=1}^n\frac{1}{4j} \ge \left(\sum_{j=1}^n \frac{a_j}{2\sqrt{j}}\right)^2.$$ Thus, it suffices to prove that $$\sum_{j=1}^n \frac{a_j}{2\sqrt{j}} > \sum_{j=1}^n\frac{1}{4j}.$$ Also, using summation by parts, we have $$\begin{align*} \sum_{j=1}^n \frac{a_j}{2\sqrt{j}} &= \sum_{j=1}^n \left(\frac{1}{2\sqrt{j}} - \frac{1}{2\sqrt{j + 1}}\right)\sum_{i=1}^j a_i + \frac{1}{2\sqrt{n + 1}}\sum_{i=1}^n a_i\\ &\ge \sum_{j=1}^n \left(\frac{1}{2\sqrt{j}} - \frac{1}{2\sqrt{j + 1}}\right)\sqrt{j} + \frac{1}{2\sqrt{n + 1}}\cdot\sqrt{n}\\ &= \frac{n}{2} + \frac{\sqrt{n}}{2\sqrt{n + 1}} - \frac12\sum_{j=1}^n \frac{\sqrt{j}}{\sqrt{j + 1}}. \end{align*}$$ It suffices to prove that $$\frac{n}{2} + \frac{\sqrt{n}}{2\sqrt{n + 1}} - \frac12\sum_{j=1}^n \frac{\sqrt{j}}{\sqrt{j + 1}} > \sum_{j=1}^n\frac{1}{4j}$$ which can be proved by Mathematical Induction. Remark: There is some similarity between this problem and the following: Problem 1: Let $a_1, a_2, \cdots > 0$ with $a_1 + a_2 + \cdots + a_n \le n^2$ for each $n \in \mathbb{N}_{>0}$. Prove that, for each $n \in \mathbb{N}_{> 0}$, $$1/a_1 + 1/a_2 + \cdots + 1/a_n \ge \frac14\log_2 n.$$ https://artofproblemsolving.com/community/c6h2726086p23746406 My proof for Problem 1 (in the link above):

Cezar Lupu wrote: Darij, it's not Karamata's inequality. Actually this is called Hardy-Littlewood-Polya inequality. Yes, according to https://artofproblemsolving.com/community/c6h14975, Karamata published later than Hardy,Littlewood and Polya, and in any case majorization was independently discovered many times before and after all these publications. There is a history in Marshall and Olkin's book on majorization. In the Anglo-Saxon countries it is called "majorization inequality" or "Hardy-Littlewood-Polya" majorization inequality". The similar thing: 1) Cauchy inequality: before I called "Cauchy-Schwarz", now I call "Cauchy-Bunyakovsky-Schwarz"

2) Holder inequality: In a book, I saw: 【In 1998, L. Maligranda said it should be called Roger-Holder inequality since Roger discovered it one year earlier than Holder.】