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