1
$\begingroup$

So I was reading up on Chebyshev's Sum Inequality, and I was a little confused about the first proof presented on Wikipedia. Specifically, the line which reads "opening the brackets". What does this phrase mean exactly, and how does the author transition to the next line?

https://en.wikipedia.org/wiki/Chebyshev%27s_sum_inequality

Thank you!

$\endgroup$
1
$\begingroup$

The Rearrangement inequality says:

Let $a_1\ge\dots\ge a_n$ and $b_1\ge\dots\ge b_n$. For all permutation $\sigma\in S_n$ prove that: $$\sum_{i=1}^na_ib_{n-i+1}\le\sum_{i=1}^na_ib_{\sigma(i)}\leq\sum_{i=1}^na_ib_i.$$

We see that $\sum\limits_{i=1}^na_ib_i$ is a biggest sum between all sums as $\sum\limits_{i=1}^na_ib_{\sigma(i)}$.

Thus, after opening the brackets we obtain: $$n\sum\limits_{i=1}^na_ib_i\geq\sum_{i=1}^na_i\sum_{i=1}^nb_i.$$ We took here all only cyclic permutations of $(1,2,...,n).$

For example.

Let $a\geq b\geq c$ and $x\geq y\geq z$.

Thus, by Rearrangement $$3(ax+by+cz)\geq(a+b+c)(x+y+z)$$ because after opening the brackets we obtain: $$(a+b+c)(x+y+z)=(ax+by+cz)+(ay+bz+cx)+(az+bx+cy)\leq$$ $$\leq(ax+by+cz)+(ax+by+cz)+(ax+by+cz)=3(ax+by+cz).$$

$\endgroup$
1
$\begingroup$

\begin{align} \sum_j \sum_k (a_j - a_k)(b_j - b_k) &= \sum_j \sum_k (a_j b_j - a_k b_j - a_j b_k + a_k b_k) \\ &= \sum_j n a_j b_j - \sum_j \sum_k a_k b_j - \sum_j \sum_k a_j b_k + \sum_k n a_k b_k \\ &= \cdots \end{align}

$\endgroup$

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.