IMO 2006, A4 Problem, Idea behind the proof

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$.
• What do you mean by $S_{ij}$? – Simeon Y. Sep 19 '17 at 10:23
• @Simeon Y In our case $S_{ij}=\frac{\sum\limits_{k=1}^na_k}{a_i+a_j}-1>0$ – Michael Rozenberg Sep 19 '17 at 10:24