0
$\begingroup$

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.

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

It is a standard Inequality and there are numerous proofs if I am not mistaken. I'll give you two options. One I'll give you a hint and you can pursue a solution on your own which will help you. But if you have a million exercises following this and using this inequality then you can choose to just refer this Wikipedia page which contains a simple proof.

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.

$\endgroup$
  • $\begingroup$ Splendid. I am absolutely embarrassed for being unable to get any results from google on this inequality. Thanks! $\endgroup$ – Yiyuan Lee Mar 2 '14 at 9:13

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.