IMO 2006, Problem A4, page 13:

Prove the inequality: $$ \sum_{i<j} \frac{a_{i}a_{j}}{a_{i}+ a_{j}} \le \frac{n}{2(a_{1} + a_{2} + \cdots + a_{n}) }\sum_{i<j}a_{i}a_{j} $$ for positive real numbers $a_{1}$, $a_{2}$, ..., $a_{n}$.

Solution (when I try to hide it, I've got the formlas broken - sorry)

Let $S = \sum\limits_{i} a_{i}$. Denote by $L$ and $R$ the expressions on the left and right hand side of the proposed inequality. We transform $L$ and $R$ using the identity: $$ \sum_{i < j} (a_{i} + a_{j}) = (n-1) \sum_{i}a_{i}. $$ And thus: $$ L = \sum\limits_{i<j} \frac{a_{i}a_{j}}{a_{i} + a_{j}} = \frac{n-1}{4} S - \frac{1}{4}\sum_{i < j} \frac{ (a_{i} - a_{j})^2}{a_{i} + a_{j}}. $$ To represent $R$ we express the sum $\sum\limits_{i<j}a_{i}a_{j}$ in two ways: $$ \sum_{i<j} a_{i}a_{j} = \frac{1}{2}\left(S^2 - \sum_{i} a_{i}^2\right) $$ $$ \sum_{i<j}a_{i}a_{j} = \frac{n-1}{2} \sum_{i}a_{i}^2 - \frac{1}{2}\sum_{i<j}(a_{i} - a_{j})^2. $$ Multiplying the first of these equalities by n-1 and adding the second one we obtain $$ n\sum_{i<j}a_{i}a_{j} = \frac{n-1}{2} S^2 - \frac{1}{2}\sum_{i<j}(a_{i} - a_{j})^2 $$ Hence $$ R = \frac{n}{2S} \sum_{i<j}a_{i}a_{j} = \frac{n-1}{4}S - \frac{1}{4}\sum_{i<j}\frac{(a_{i} - a_{j})^2}{S} $$ Now compare the last two equalities. Since $S \ge a_{i} + a_{j}$ for any $i<j$, the claim $L \ge R$ results.

My question: what is the idea behind this proof, and how to think it out?


The idea behind this proof: try to rewrite our inequality in the following form: $$\sum_{1\leq i<j\leq n}(a_i-a_j)^2S_{ij}\geq0$$ and to hope that $S_{ij}\geq0$.

This method names SOS (Sum Of Squares). It's a very useful method.

See here:

https://math.stackexchange.com/tags/sos/info https://math.stackexchange.com/questions/tagged/sos

  • $\begingroup$ What do you mean by $S_{ij}$? $\endgroup$ – Simeon Y. Sep 19 '17 at 10:23
  • $\begingroup$ @Simeon Y In our case $S_{ij}=\frac{\sum\limits_{k=1}^na_k}{a_i+a_j}-1>0$ $\endgroup$ – Michael Rozenberg Sep 19 '17 at 10:24
  • $\begingroup$ Oh, thank you! That is very helpful comment! $\endgroup$ – Simeon Y. Sep 19 '17 at 10:26
  • $\begingroup$ @Simeon Y You are welcome! $\endgroup$ – Michael Rozenberg Sep 19 '17 at 10:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.