Is it your inequality, Harazi? I had no idea up to this point. It's really unconventional, and this is what makes it great. Well, here's my solution, though it is similar to others that I have heard from the students who took that TST. First, we will prove a lemma. For any real numbers $a_1,a_2,...,a_{2k+1}$ we have \[(a_1+a_3+a_5+...+a_{2k+1})^2 \leq \sum_{1\leq i \leq j \leq n} (a_i+...+a_j)^2\] This is simple to prove, just by denoting $a_1+a_2+...+a_i$ with $S_i$ and opening the parenthesis. Now for our problem. Call a succession of consecutive $a_i$'s a "sequence". Call a sequence that is missing from $S$ a "gap". Thus, our set $S$ will be formed by a sequence, followed by a gap, then another sequence, then a gap,..., and at last a sequence. That is why $S$ will look like this: \[\{a_{i_1},a_{i_1+1},...,a_{i_1+\alpha_1}; a_{i_2},a_{i_2+1},...,a_{i_2+\alpha_2};...;a_{i_k},a_{i_k+1},...,a_{i_k+\alpha_k}\}\] where the $\alpha_j$'s are non-negative, and for every $j$ we have $i_j+\alpha_j<i_{j+1}-1$. This is how we write $S$ as a sequence, then a gap, then another sequence,..., and at last a sequence. Now let $s_1=a_{i_1}+a_{i_1+1}+...+a_{i_1+\alpha_1}$, the sum of the first sequence; $s_2=a_{i_1+\alpha_1+1}+...+a_{i_2-1}$, the sum of the first gap; $s_3=a_{i_2}+a_{i_2+1}+...+a_{i_2+\alpha_2}$, the sum of the second sequence; ... $s_{2k-1}=a_{i_k}+a_{i_k+1}+...+a_{i_k+\alpha_k}$, the sum of the $k$-th sequence; But then the sum in LHS becomes $(s_1+s_3+...+s_{2k-1})^2$, which the lemma tells us is at most $\sum_{1\leq i \leq j \leq 2k-1} (s_i+...+s_j)^2$. The terms of this latter sum are obviously among the terms in RHS, and thus follows that $LHS \leq RHS$.

Yes, Andrei, it's my problem. It may be great, but your solution is greater. And I really do not know what other students who took that TST said, but I didn't find similar solutions. Mircea Becheanu and me wouldn't have been idiot not to give them points if they had a similar idea. There were some " similar" ideas, but they were far from the solution of the problem. They may have thought about this solution, but they didn't write that.

Hi, I was wondering if you can prove this inequality by induction on n. I think by defining b_i=a_i+..a_n and using induction the problem can be solved. Do you have any idea? Thx, Amir[/tex]

Hi, I'm interested in your initial solution, Harazi. By the way, how did you come up with this problem?

Amirdana wrote: Hi, I was wondering if you can prove this inequality by induction on n. I think by defining b_i=a_i+..a_n and using induction the problem can be solved. Do you have any idea? I belive that it cannot be solved using induction. I think that Harazi has the same opinion.

Valentin Vornicu wrote: Amirdana wrote: Hi, I was wondering if you can prove this inequality by induction on n. I think by defining b_i=a_i+..a_n and using induction the problem can be solved. Do you have any idea? I belive that it cannot be solved using induction. I think that Harazi has the same opinion. i might have a diff opinion.. i mean i didn't come up with a solution for the ineq during the contest or afterwards, but it came to my attention a super-solution, given in contest though not to well explained... so here goes: Lemma $2ab\leq (a+L+b)^2+L^2$... duuuh suppose $a_1\in S$. Else we "eliminate" all terms containing $a_1$ in the right side of the inequality and carry on by induction... Now 2 cases: 1. $a_2\in S$ then denote $a_1'=a_1+a_2$ and prove the inequality for $a_1'$, $a_3$... $a_n$ and $S'=S\cup \{a_1'\}\setminus \{a_1,a_2\}$... 2. $a_2\not\in S$ then we eliminate $a_1^2$ from the left side with the one from the right. We use the lemma for $L=a_2+...+a_{k-1}$ we have that : $2a_1\cdot a_k\leq (a_1+(a_2+...+a_{k-1})+a_k)^2+(a_2+...+a_{k-1})^2$ for any $k>2$ with $a_k\in S$. We add these inequalities up with the ineq from induction for $a_3$, ... ,$a_n$ and $S'=S\setminus \{a_1\}$ which contains no $a_1$ or $a_2$ terms.... $a_1^2+\sum 2a_1\cdot a_k +(a_{i_1}+...+a_{i_t})^2\leq \sum (a_i+...a_j)^2$ with $i_1>2$... The soln is harder to follow because it is inductive (rather recursive) but the main idea is that we completely "eliminate" all terms that contain $a_1$ and / or $a_2$ from both sides and prove the ineq for $n-2$... Amirdana, i tried your idea during the contest and it didn't help.. but who knows?

I also also solved it in abeautiful way. I'll send my solution later.

Well,dear Kappa my solution is same as yours. To Harazi: I can say it's the most beautiful problem I have ever solved. How did you designed this problem???? _____________________ No,pain,no gain

Omid Hatami wrote: Well,dear Kappa my solution is same as yours. i'm glad that other people thought about this solution; i also know that the bulgarian BMO (Balkan Math Oly) Leader gave the same solution to it. One observation though: it's not my solution, i heard it from a guy that gave it during contest.

I see that this topic is of great interest and I have some lots of comments. First of all, yes, I made a terribile mistake and didn't understand what Dragos Mihnea wrote during the contest and gave him a big 0. I must admit, I was an idiot. But don't worry, his beautiful solution received 6 points in the end. This solution is absolutely magnificient and shows that the problem can be solved with induction. Now, how did I come up with this problem? Well, not very easy. I was playing around with the inequality $ a^2+b^2\geq 2ab$ and some identities and after two days the problem became this. Maybe some of you won't believe me and will say it is copied from somewhere. If anyone finds it anywhere, I sincerely apologise to that men who invented it. Till then, I think I invented it. And my solution is far more artificial than the solutions presented here. The conclusion: I'm very glad that inequalities problems can be pleasant sometimes.

I think this problem is terrifying at first sight, but it should be trivial after taking the following substitution. Take $ a_0$ a real, and define a sequence $ {x_n}$ as follows: $ x_k = a_0 + a_1 \ldots + a_k,k = 0,1,\ldots,n$ and by Lagrange's formula, $ \sum_{1\leq i \leq j \leq n } (a_i + \cdots + a_j ) ^2 = \sum_{0 \leq i < j \leq n}(x_i - x_j)^2$. Next we take a look at the left side. $ LHS = \left( \sum_{i \in S} a_i \right)^2 = (\sum_{i \in S}(x_{i - 1} - x_i))^2$.$ (1)$ Note that the previous sum can be written as follows: $ (\sum_{j = 1}^{t}(x_{ij}( - 1)^j))^2$, where $ t = 2k$ is even. For the many squares in $ (1)$, we only deals with those contains only $ x_{ij}$. And the question becomes $ (y_1 - y_2 + y_3 - \ldots + y_{2k - 1} - y_{2k})^2 \leq \sum_{1\leq i < j \leq 2k}(y_i - y_j)^2$, where $ y_j = x_{ij}$ or $ (y_1 - y_2 + y_3 - \ldots + y_{2k - 1} - y_{2k})^2 \leq 2k(y_1^2 + \ldots + y_{2k}^2) - (y_1 + \ldots + y_{2k})^2$. This becomes obvious if we write it as $ (y_1 + y_3 + \ldots + y_{2k - 1})^2 + (y_2 + y_4 + \ldots + y_{2k})^2 \leq k(y_1^2 + y_2^2 + \ldots + y_{2k}^2)$, which is a straightforward consequence of Cauchy's. Is this clear?

Valentin Vornicu wrote: Let $ n\geq 2$ be an integer and let $ a_1,a_2,\ldots,a_n$ be real numbers. Prove that for any non-empty subset $ S\subset \{1,2,3,\ldots, n\}$ we have \[ \left( \sum_{i \in S} a_i \right)^2 \leq \sum_{1\leq i \leq j \leq n } (a_i + \cdots + a_j ) ^2 .\] Gabriel Dospinescu ^What if you take $ n = 3$; $ S = \{1,3\}$; $ a_1,a_3 = - 2; a_2 = 1,$ ? $ (a_1 + a_3)^2 \leq (a_1 + a_2)^2 + (a_2 + a_3)^2 + (a_1 + a_2 + a_3)^2$ $ ( - 2 - 2)^2 \leq ( - 2 + 1)^2 + (1 - 2)^2 + ( - 2 - 2 + 1)^2$ $ 16 \leq 1 + 1 + 9$ :

MathUniverse wrote: Valentin Vornicu wrote: Let $ n\geq 2$ be an integer and let $ a_1,a_2,\ldots,a_n$ be real numbers. Prove that for any non-empty subset $ S\subset \{1,2,3,\ldots, n\}$ we have \[ \left( \sum_{i \in S} a_i \right)^2 \leq \sum_{1\leq i \leq j \leq n } (a_i + \cdots + a_j ) ^2 .\] Gabriel Dospinescu ^What if you take $ n = 3$; $ S = \{1,3\}$; $ a_1,a_3 = - 2; a_2 = 1,$ ? $ (a_1 + a_3)^2 \leq (a_1 + a_2)^2 + (a_2 + a_3)^2 + (a_1 + a_2 + a_3)^2$ : The RHS also includes the terms with $ i=j$

spanferkel wrote: MathUniverse wrote: Valentin Vornicu wrote: Let $ n\geq 2$ be an integer and let $ a_1,a_2,\ldots,a_n$ be real numbers. Prove that for any non-empty subset $ S\subset \{1,2,3,\ldots, n\}$ we have \[ \left( \sum_{i \in S} a_i \right)^2 \leq \sum_{1\leq i \leq j \leq n } (a_i + \cdots + a_j ) ^2 .\] Gabriel Dospinescu ^What if you take $ n = 3$; $ S = \{1,3\}$; $ a_1,a_3 = - 2; a_2 = 1,$ ? $ (a_1 + a_3)^2 \leq (a_1 + a_2)^2 + (a_2 + a_3)^2 + (a_1 + a_2 + a_3)^2$ : The RHS also includes the terms with $ i = j$ I see now... sorry...

andrei negut wrote: Is it your inequality, Harazi? I had no idea up to this point. It's really unconventional, and this is what makes it great. Well, here's my solution, though it is similar to others that I have heard from the students who took that TST. First, we will prove a lemma. For any real numbers $ a_1,a_2,...,a_{2k + 1}$ we have \[ (a_1 + a_3 + a_5 + ... + a_{2k + 1})^2 \leq \sum_{1\leq i \leq j \leq n} (a_i + ... + a_j)^2\] This is simple to prove, just by denoting $ a_1 + a_2 + ... + a_i$ with $ S_i$ and opening the parenthesis. Now for our problem. Call a succession of consecutive $ a_i$'s a "sequence". Call a sequence that is missing from $ S$ a "gap". Thus, our set $ S$ will be formed by a sequence, followed by a gap, then another sequence, then a gap,..., and at last a sequence. That is why $ S$ will look like this: \[ \{a_{i_1},a_{i_1 + 1},...,a_{i_1 + \alpha_1}; a_{i_2},a_{i_2 + 1},...,a_{i_2 + \alpha_2};...;a_{i_k},a_{i_k + 1},...,a_{i_k + \alpha_k}\}\] where the $ \alpha_j$'s are non-negative, and for every $ j$ we have $ i_j + \alpha_j < i_{j + 1} - 1$. This is how we write $ S$ as a sequence, then a gap, then another sequence,..., and at last a sequence. Now let $ s_1 = a_{i_1} + a_{i_1 + 1} + ... + a_{i_1 + \alpha_1}$, the sum of the first sequence; $ s_2 = a_{i_1 + \alpha_1 + 1} + ... + a_{i_2 - 1}$, the sum of the first gap; $ s_3 = a_{i_2} + a_{i_2 + 1} + ... + a_{i_2 + \alpha_2}$, the sum of the second sequence; ... $ s_{2k - 1} = a_{i_k} + a_{i_k + 1} + ... + a_{i_k + \alpha_k}$, the sum of the $ k$-th sequence; But then the sum in LHS becomes $ (s_1 + s_3 + ... + s_{2k - 1})^2$, which the lemma tells us is at most $ \sum_{1\leq i \leq j \leq 2k - 1} (s_i + ... + s_j)^2$. The terms of this latter sum are obviously among the terms in RHS, and thus follows that $ LHS \leq RHS$. How did you make such a trivial conclusion? Where do you have $ (s_1+s_3)^2$ on the RHS? :

He means the terms of $ \sum_{1\leq i\leq j\leq 2k-1}(s_{i}+...+s_{j})^{2}$ are among those of the original RHS $ \sum_{1\leq i\leq j\leq n}(a_{i}+...+a_{j})^{2}$

spanferkel wrote: He means the terms of $ \sum_{1\leq i\leq j\leq 2k - 1}(s_{i} + ... + s_{j})^{2}$ are among those of the original RHS $ \sum_{1\leq i\leq j\leq n}(a_{i} + ... + a_{j})^{2}$ They are not. Where do you have let's say $ (s_1+s_3)^2$ on the RHS if the gap is between $ s_1$ and $ s_3$ ?

In the lemma there are only terms like $ (s_1+s_2+s_3)^2$ on the RHS. No gaps. (And $ i$ and $ j$ are not necessarily odd!) The $ s_i$ are adjacent. That is the advantage of this estimation

spanferkel wrote: In the lemma there are only terms like $ (s_1 + s_2 + s_3)^2$ on the RHS. No gaps. (And $ i$ and $ j$ are not necessarily odd!) The $ s_i$ are adjacent. That is the advantage of this estimation Thanks, I've misunderstood lemma...

Sorry for revive, but I do not understand the solution by andrei negut. My questions now: I don't get this: andrei negut wrote: The terms of this latter sum are obviously among the terms in RHS, and thus follows that $LHS \leq RHS$.

It is obviously false. how could $\sum_{1\leq i \leq j \leq 2k-1} (s_i+...+s_j)^2 \leq \sum_{1\leq i \leq j \leq n} (a_i+...+a_j)^2$? For rchich's solution,

I don't get that part about $x_{ij}$. Is that x sub (product of i and j)? So $ (\sum_{j = 1}^{t}(x_{ij}( - 1)^j))^2$ is equal to $-x_i+x_{2i}-x_{3i}+...+x_{ti}$? How could that be equal to $(\sum_{i \in S}(x_{i - 1} - x_i))^2$? What does he mean by "those than only contain $x_ij$?

Valentin Vornicu wrote: Let $n\geq 2$ be an integer and let $a_1,a_2,\ldots,a_n$ be real numbers. Prove that for any non-empty subset $S\subset \{1,2,3,\ldots, n\}$ we have \[ \left( \sum_{i \in S} a_i \right)^2 \leq \sum_{1\leq i \leq j \leq n } (a_i + \cdots + a_j ) ^2 . \]Gabriel Dospinescu I have roughly the same solution as andrei, although I think it's more motivated in the form that follows. I think rchlch has an equivalent solution. The "reduction" optimization I mention below is the same in all three of these solutions; it is annoying to write up correctly but it is a quite natural idea. We proceed by induction on $n \ge 1$ (but the induction is superficial here; it's just to formalize an optimization argument), with base case $n=1$ being immediate. Now for a given $n$ we consider the following three cases. If there is $k$ such that $k, k+1 \in S$, then we can reduce to the $n-1$ case by combining $a_k + a_{k+1}$ into a single variable, discarding the terms of the right-hand side which contain exactly one of the two. Similarly, if $k, k+1 \notin S$ (even $k=0$ and $k=n$) then we again reduce to $n-1$ by the same technique. Thus by doing the above optimizations, the only case left to consider is $n$ odd and $S = \{1, 3, 5, \dots, n\}$. Denote $y_k = a_1 + \dots + a_k$ for $0 \le k \le n$, then this reduces to the inequality \[ \left( y_n - y_{n-1} + y_{n-2} - y_{n-3} + \dots + y_1 - y_0 \right)^2 \le \sum_{0 \le i < j \le n} (y_j - y_i)^2. \]If we expand this, we can rewrite the inequality as \[ \sum_{\substack{0 \le i < j \le n \\ i+j \text{ even}}} y_iy_j \le \frac{n-1}{4} \sum_{0 \le i \le n} y_i^2. \]But this follows by simply summing the two obvious inequalities \[ \sum_{\substack{0 \le i < j \le n \\ i,j \text{ even}}} y_iy_j \le \frac{n-1}{4} \sum_{\substack{0 \le i \le n \\ i \text{ even}}} y_i^2 \qquad\text{and}\qquad \sum_{\substack{0 \le i < j \le n \\ i,j \text{ odd}}} y_iy_j \le \frac{n-1}{4} \sum_{\substack{0 \le i \le n \\ i \text{ odd}}} y_i^2. \]

The equality cases are as follows 1. $n=1$. 2. $a_1=a_2=...=a_n=0$ 3. $n=2k-1$ for some positive integer $k$, $ S=\{1,3,...,2k-1\}$, $a_1=a_3=...=a_{2k-1}=c$, and $a_2=a_4=...=a_{2k-2}=-c$.

My solution is essentially the same as that of andrei and v_Enhance, with no clever optimisations, hence I find it easier (but less elegant) to come up with Valentin Vornicu wrote: Let $n\geq 2$ be an integer and let $a_1,a_2,\ldots,a_n$ be real numbers. Prove that for any non-empty subset $S\subset \{1,2,3,\ldots, n\}$ we have \[ \left( \sum_{i \in S} a_i \right)^2 \leq \sum_{1\leq i \leq j \leq n } (a_i + \cdots + a_j ) ^2 . \]Gabriel Dospinescu Let us introduce variables $s_k=\left(\sum^k_{i=1} a_i \right)$ for all $k \ge 1$ and set $s_0=0$; as we typically do for empty sums. Notice that $$\sum_{1 \le i \le j \le n} (a_i+\dots+a_j)^2=\sum_{0 \le i \le j \le n} \left(s_i-s_j \right)^2.$$Note also that $S$ can be written as a union of contiguous blocks of integers; hence, we can find $0 \le i_1<i_2<\dots<i_{2m} \le n$ for which $$\left(\sum_{i \in S} a_i \right)=\left(\left(\sum^m_{j=1} s_{i_{2j}} \right)-\left(\sum^m_{j=1} s_{i_{2j-1}} \right)\right).$$We present the following assertion which we shall invoke to complete the argument. Claim: For any $m \ge 1$ and real numbers $s_1, \dots, s_{2m}$, we have $$\left( \left(\sum^m_{j=1} s_{2j-1} \right)-\left(\sum^m_{j=1} s_{2j} \right) \right)^2 \le \sum_{0 \le i \le j \le 2m} (s_i-s_j)^2,$$where $s_0=0$ by convention. (Proof) For brevity, let $A=\left(\sum^m_{j=1} s_{2j-1}\right), B=\left(\sum^m_{j=1} s_{2j}\right)$ and $C=A+B$; also, let $M=\left(\sum^m_{j=1} s_{2j-1}^2\right)$ and $N=\left(\sum^m_{j=1} s_{2j}^2 \right)$. Now, $$ \sum_{0 \le i \le j \le 2m} (s_i-s_j)^2=2m \cdot (M+N)-C^2 \ge 2(A^2+B^2)-C=(A-B)^2,$$as desired. $\blacksquare$ To conclude; in the original problem, neglect all terms on the RHS except pairs of the form $(i_s, i_r)$ and then apply the claim. $\blacksquare$

Let $s_i = a_1 + a_2 + \cdots + a_i$ for each $1 \le i \le n$, and set $s_0 = 0.$ Observe that the RHS is equal to $\sum_{0 \le i < j \le n} (s_i - s_j)^2.$ Observe that the sum of any subset of the $a_i$'s is a difference between the sum of some $k$ of the $s_i$'s and some other $k$ of the $s_i$'s, for some $k \in \mathbb{N}.$ Suppose that $A, B$ are disjoint subsets of the $s_i$'s with size $k$, so that the LHS is $(\sum_{x \in A} x - \sum_{x \in B} x)^2$. Let $a, b$ be the average of the things in $A, B$ respectively. Then the LHS is $k^2(a-b)^2.$ Now notice that $\sum_{x \in A, y \in B} (x-y)^2 \le RHS.$ We claim that $\sum_{x \in A, y \in B} (x-y)^2 \ge k^2(a-b)^2$, which would clearly suffice. Indeed, this is pretty obvious by smoothing. $\square$