The theorem states that the sum S=a1b1+...+anbnS=a1b1+...+anbn is a maximum if two strings a1,...,ana1,...,an and b1,...,bnb1,...,bn have the same order. Let's assume a1The proof from my book is this one ( the same I sensed at the first glance):
Let ar>as(br>bs)ar>as(br>bs). Consider the sums:
S1=a1b1+...+arbr+...+asbs+...+anbn,S1=a1b1+...+arbr+...+asbs+...+anbn,
S2=a1b1+...+arbs+...+asbr+...+anbn.S2=a1b1+...+arbs+...+asbr+...+anbn.
We obtain S2S2 from S1S1 by replacing bsbs with brbr. Hence
S2−S1=arbs+asbr−arbr−asbs=(ar−as)(bs−br)<0S2−S1=arbs+asbr−arbr−asbs=(ar−as)(bs−br)<0
We deduce that S1>S2S1>S2.
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 rr and ss in the strings ( denoted by ii, rS3=a1b1+...+arbs+...+aibr+...+asbi+...+anbn.S3=a1b1+...+arbs+...+aibr+...+asbi+...+anbn.
This sum is bigger than S2S2 if you try to prove it.
Even though I could prove that S3>S1S3>S1, 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!
