Let $a_1 \leq a_2 \leq \cdots \leq a_n$ and $b_1 \leq b_2 \leq \cdots \leq b_n$, then prove that $$n\sum_{i=1}^n a_ib_i \geq \sum_{i=1}^n a_i \cdot \sum_{i = 1}^n b_i.$$


The $n\displaystyle \sum_{i=1}^n a_ib_i$ makes me think of Cauchy-Schwarz but I am not sure how to use it. I could use AM-GM to say $n\displaystyle \sum_{i=1}^n a_ib_i \leq n\displaystyle \sum_{i=1}^n \dfrac{(a_i+b_i)^2}{4}$, but I am not sure how to relate that to the other terms.

  • $\begingroup$ Maybe need the restriction that the a's and b's are all nonnegative, or maybe all positive. $\endgroup$ – coffeemath Jan 3 '16 at 4:28
  • 1
    $\begingroup$ You don't. Maybe that is a hint to use the rearrangement inequality? $\endgroup$ – user19405892 Jan 3 '16 at 4:29
  • $\begingroup$ Induction works. $\endgroup$ – Winther Jan 3 '16 at 4:31
  • $\begingroup$ @Winther Yes, but there may be a more clever way using inequalities. $\endgroup$ – user19405892 Jan 3 '16 at 4:32
  • 4
    $\begingroup$ Check en.wikipedia.org/wiki/Chebyshev%27s_sum_inequality $\endgroup$ – Macavity Jan 3 '16 at 4:36

Observe that \begin{align*} \sum_{i=1}^n a_i \sum_{i=1}^n b_i - n \sum_{i=1}^n a_ib_i &=\sum_{i,j=1}^na_ib_j - n \sum_{i=1}^n a_ib_i\\ &=\frac{1}{2}\left[\sum_{i, j=1}^n(a_ib_j + a_j b_i) - \sum_{i, j=1}^n(a_ib_i +a_jb_j) \right]\\ &=\frac{1}{2}\sum_{i, j=1}^n(a_ib_j+a_jb_i-a_ib_i-a_jb_j)\\ &=-\frac{1}{2}\sum_{i, j=1}^n(a_j-a_i)(b_j-b_i)\\ &\le 0. \end{align*}


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.