# Inequality in non-decreasing sequence

Let $a, b$ be two sequences of real numbers such that $a_1 \le a_2 \le \dots \le a_n$ and $b_1 \le b_2 \le \dots \le b_n$. Prove (or disprove) that

$$\left(\frac{1}{n}\sum_{i=1}^{n}{a_i}\right)\left(\frac{1}{n}\sum_{i=1}^{n}{b_i}\right) \le \left(\frac{1}{n}\sum_{i=1}^{n}{a_ib_i}\right)$$

Now obviously, I have no idea from where to even start attacking this monster. I tried Cauchy-Schwarz (square roots of $a_i$ and $b_i$), and by using AM-GM on the left side, but realized that they are not necessarily non-negative.

• This is Chebyshev's inequality. Hint: use rearrangement to prove. – Macavity Mar 2 '14 at 8:43

Hint: Consider the sum $$\sum_{i = 1}^n \sum_{j = 1}^n(a_i - a_j)(b_i - b_j)$$
Since we know that $\{a_k\}$ and $\{b_k\}$ are monotonically increasing and since either $i \le j$ or $i \gt j$ the signs of the two facotrs $(a_i - a_j)$ and $(b_i - b_j)$ will always be the same and hence the iterated sum will be non-negative. Now you have an inequality. Expand and continue.