The memory that I considered this question a long time ago was jogged by my perusing an earlier one about whether a product is always greater than a sum.

If you have two sequences of real positive numbers, all greater than 1, and each sequence increasing with increasing index $k$

$$a_k , k \in {0 ... n}$$

&

$$b_k , k \in {0 ... n} , $$

and if the elements are multiplied together itemwise & the products summed, is the maximum always

$\sum_{k=0}^n a_k b_k$

and the minimum always

$\sum_{k=0}^n a_k b_{n-k}$?

It would seem so, merely casting it in the mind ... but I can't see how it would be rigorously proven ... nor am I absolutely sure it's absolutely true, either.

  • 2
  • Is that the name for this theorem that I've asked for verification & proof of? I thought it probably would have a name & be a theorem ... but I just couldn't find it anywhere! – AmbretteOrrisey Nov 15 at 6:27
  • Seen it now - thanks for that. And you don't even need the >1 condition! – AmbretteOrrisey Nov 15 at 6:30

First consider the simplest nontrivial case, $n=2$. Let $a_1>a_0$ and $b_1>b_0$. Then $(a_1-a_0)(b_1-b_0)>0$, which simplifies to $a_0b_0+a_1b_1>a_0b_1+a_1b_0$, which is what we want.

Now let $n>2$. Without loss of generality, fix $a$ in its sorted permutation and consider permutations of $b$. If $b$ is not sorted, then there are two indices that are out of order, and the $n=2$ lemma proves that we can increase the product by swapping those two indices. Therefore only the sorted order of $b$ maximizes the product. For the same reason, only the anti-sorted order of $b$ minimizes the product.

(You could toss a bunch of index notation at the previous paragraph to make it look more formal.)

  • That looks like an answer, that does. I'll scrutinise it ... but it has a solid look about it. – AmbretteOrrisey Nov 15 at 1:27
  • Oh ... thankyou, by the way! – AmbretteOrrisey Nov 15 at 1:28
  • You're welcome! – Chris Culter Nov 15 at 21:18

Yes. Start with $n=1$ so there are two items in each list. Note that $$(a_0b_0+a_1b_1) - (a_0b_1+a_1b_0)=a_1(b_1-b_0)-a_0(b_1-b_0)\gt 0$$ For longer lists, you can use the same argument to swap any pair that is out of order and increase the sum.

  • Yes - the other guy said essentially the same thing. It's essentially proving it for $n=1$ (two items), then proceeding by induction thence to arbitrary n. Thankyou! – AmbretteOrrisey Nov 15 at 1:30
  • Or maybe not induction strictly speaking ... but showing that by applying the two-item case repeatedly until they are both in sorted order always increases the sum of products as defined. – AmbretteOrrisey Nov 15 at 1:37

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.