# Help me complete the proof of the Rearrangement Inequality.

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

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.