1
$\begingroup$

I am following the proof given by on this link. So given two non-decreasing sequences $$ a_1\leq a_2\leq a_3......\leq a_n \\ b_1\leq b_2\leq b_3......\leq b_n.$$ Let, $(a'_1,.... a'_n)$ be a permutation of $(a_1,.... a_n)$. Then the following inequality holds: $a_1b_1+.....+a_nb_n\geq a'_1b_1+.....+a'_nb_n.$

Proof: Consider the sum $S=a_1b_1+..+a_rb_r+..+a_sb_s..+a_nb_n$ and $S'=a_1b_1+..+a_sb_r+..+a_rb_s..+a_nb_n.$ Now on taking the difference $S-S'$ we observe that $S-S'\geq0.$ After this, the person in the video says that since every permutation is a sequence of transpositions and therefore the sum $S$ is maximal. I understand this statement intuitively, but if I were to write formally (say, in an exam) how should I go about proving the theorem after I have shown that $S\geq S'.$

$\endgroup$
2
$\begingroup$

I would do it by contradiction.

Out of all permutations of $a_1,a_2,\dots,a_n$ let $c_1,c_2\dots c_n$ be one that maximizes $c_1b_1+c_2b_2+ \dots + c_nb_n$.

We must prove $c_1\leq c_2\dots \leq c_n$. Suppose not, then $c_i>c_{i+1}$ for some $i\in{1,2\dots n-1}$. Which is a contradiction.

$\endgroup$
1
$\begingroup$

Well you could start with induction method. Let's say true for k<=n, consider the k=n+1 case. If the multiplier of bn is an, then it is simply the k=n case. If the multiplier of bn is a_t, interchange the a_n with a_t, and let a_t fitting into where a_n belongs to(b_s let's say). By this transformation, the whole value would increase. And then use the induction, which is also a k=n case.

$\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.