The theorem states that the sum $S=a_1b_1 + . . . + a_nb_n$ is a maximum if two strings $a_1,...,a_n$ and $b_1,...,b_n$ have the same order. Let's assume $a_1<a_2<...<a_n$ and $b_1<b_2<...<b_n$. The proof from my book is this one ( the same I sensed at the first glance):
Let $a_r>a_s (b_r>b_s)$. Consider the sums:
$S_1=a_1b_1+...+a_rb_r+...+a_sb_s+...+a_nb_n,$
$S_2=a_1b_1+...+a_rb_s+...+a_sb_r+...+a_nb_n.$
We obtain $S_2$ from $S_1$ by replacing $b_s$ with $b_r$. Hence
$S_2-S_1=a_rb_s+a_sb_r-a_rb_r-a_sb_s=(a_r-a_s)(b_s-b_r)<0$
We deduce that $S_1>S_2$.
This is their proof. But it's not enough for me because of this: Let's assume the strings are big enough and have at least one element between the positions $r$ and $s$ in the strings ( denoted by $i$, $r<i<s$ ), where $a_1<...<a_i<...<a_n$ and $b_1<...<b_i<...<b_n$. The only way through which we can obtain from $S_2$ a bigger sum than $S_2$ using rearrangements is to interchange $b_r$ with the "$b$ factor" of one of the terms between $a_rb_s$ and $a_sb_r$ in $S_2$, i.e. $b_i$. By doing this we obtain the following sum from $S_2$:
$S_3=a_1b_1+...+a_rb_s+...+a_ib_r+...+a_sb_i+...+a_nb_n.$
This sum is bigger than $S_2$ if you try to prove it. Even though I could prove that $S_3>S_1$, it is pointless as my aim is to find the generalization in their proof or at least another general one, but I just can't seem to succeed. I hope you could help me with a proof for this problem. Thanks in advance!
We can prove it by induction.
For $n=2$ we need to prove that $$a_1b_2+a_2b_1\leq a_1b_1+a_2b_2$$ or $$(a_1-a_2)(b_1-b_2)\geq0,$$ which is obvious.
Let $\sum\limits_{i=1}^na_ib_{\sigma(i)}\leq\sum\limits_{i=1}^na_ib_i$ for all $a_1\leq a_2\leq...\leq a_n$, $b_1\leq b_2\leq...\leq b_n$ for all $n\geq2$ and $\sigma\in S_n$.
Now, let $a_1\leq a_2\leq...\leq a_n\leq a_{n+1}$, $b_1\leq b_2\leq...\leq b_n\leq b_{n+1}$ and $\sigma\in S_{n+1}$.
We'll prove that $$\sum_{i=1}^{n+1}a_ib_{\sigma(i)}\leq\sum_{i=1}^{n+1}a_ib_i.$$ If $\sigma(n+1)=n+1$ then by the induction assumption we are done.
Let $\sigma(n+1)=j$ and $\sigma^{-1}(n+1)=k$, where $j\neq n+1$.
Thus, $$a_1b_{\sigma(1)}+...+a_kb_{n+1}+...+a_{n+1}b_j\leq a_1b_{\sigma(i)}+...+a_kb_j+...+a_{n+1}b_{n+1}\leq\sum_{i=1}^{n+1}a_ib_{\sigma(i)}$$ and we are done!