Sum of Itemwise Products of Two Sets of Real Numbers
$begingroup$
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.
sequences-and-series summation
edited Nov 15 '18 at 0:53
Andrés E. Caicedo
65.8k8160252
asked Nov 15 '18 at 0:31
AmbretteOrriseyAmbretteOrrisey
54210
$endgroup$
add a comment |
$begingroup$
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.
sequences-and-series summation
edited Nov 15 '18 at 0:53
Andrés E. Caicedo
65.8k8160252
asked Nov 15 '18 at 0:31
AmbretteOrriseyAmbretteOrrisey
54210
$endgroup$
2
$begingroup$
Rearrangement inequality?
$endgroup$
– lastresort
Nov 15 '18 at 6:10
$begingroup$
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!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 6:27
$begingroup$
Seen it now - thanks for that. And you don't even need the >1 condition!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 6:30
add a comment |
$begingroup$
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.
sequences-and-series summation
edited Nov 15 '18 at 0:53
Andrés E. Caicedo
65.8k8160252
asked Nov 15 '18 at 0:31
AmbretteOrriseyAmbretteOrrisey
54210
$endgroup$
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.
sequences-and-series summation
sequences-and-series summation
edited Nov 15 '18 at 0:53
Andrés E. Caicedo
65.8k8160252
asked Nov 15 '18 at 0:31
AmbretteOrriseyAmbretteOrrisey
54210
edited Nov 15 '18 at 0:53
Andrés E. Caicedo
65.8k8160252
asked Nov 15 '18 at 0:31
AmbretteOrriseyAmbretteOrrisey
54210
edited Nov 15 '18 at 0:53
Andrés E. Caicedo
65.8k8160252
edited Nov 15 '18 at 0:53
Andrés E. Caicedo
65.8k8160252
edited Nov 15 '18 at 0:53
Andrés E. Caicedo
65.8k8160252
65.8k8160252
asked Nov 15 '18 at 0:31
AmbretteOrriseyAmbretteOrrisey
54210
asked Nov 15 '18 at 0:31
AmbretteOrriseyAmbretteOrrisey
54210
asked Nov 15 '18 at 0:31
AmbretteOrriseyAmbretteOrrisey
54210
54210
2
$begingroup$
Rearrangement inequality?
$endgroup$
– lastresort
Nov 15 '18 at 6:10
$begingroup$
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!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 6:27
$begingroup$
Seen it now - thanks for that. And you don't even need the >1 condition!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 6:30
add a comment |
2
$begingroup$
Rearrangement inequality?
$endgroup$
– lastresort
Nov 15 '18 at 6:10
$begingroup$
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!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 6:27
$begingroup$
Seen it now - thanks for that. And you don't even need the >1 condition!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 6:30
2
2
$begingroup$
Rearrangement inequality?
$endgroup$
– lastresort
Nov 15 '18 at 6:10
$begingroup$
Rearrangement inequality?
$endgroup$
– lastresort
Nov 15 '18 at 6:10
$begingroup$
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!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 6:27
$begingroup$
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!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 6:27
$begingroup$
Seen it now - thanks for that. And you don't even need the >1 condition!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 6:30
$begingroup$
Seen it now - thanks for that. And you don't even need the >1 condition!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 6:30
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
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.)
answered Nov 15 '18 at 1:20
Chris CulterChris Culter
21.5k43888
$endgroup$
$begingroup$
That looks like an answer, that does. I'll scrutinise it ... but it has a solid look about it.
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:27
$begingroup$
Oh ... thankyou, by the way!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:28
$begingroup$
You're welcome!
$endgroup$
– Chris Culter
Nov 15 '18 at 21:18
add a comment |
$begingroup$
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.
answered Nov 15 '18 at 1:21
Ross MillikanRoss Millikan
301k24200375
$endgroup$
$begingroup$
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!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:30
$begingroup$
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.
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:37
add a comment |
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2999019%2fsum-of-itemwise-products-of-two-sets-of-real-numbers%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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.)
answered Nov 15 '18 at 1:20
Chris CulterChris Culter
21.5k43888
$endgroup$
$begingroup$
That looks like an answer, that does. I'll scrutinise it ... but it has a solid look about it.
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:27
$begingroup$
Oh ... thankyou, by the way!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:28
$begingroup$
You're welcome!
$endgroup$
– Chris Culter
Nov 15 '18 at 21:18
add a comment |
$begingroup$
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.)
answered Nov 15 '18 at 1:20
Chris CulterChris Culter
21.5k43888
$endgroup$
$begingroup$
That looks like an answer, that does. I'll scrutinise it ... but it has a solid look about it.
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:27
$begingroup$
Oh ... thankyou, by the way!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:28
$begingroup$
You're welcome!
$endgroup$
– Chris Culter
Nov 15 '18 at 21:18
add a comment |
$begingroup$
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.)
answered Nov 15 '18 at 1:20
Chris CulterChris Culter
21.5k43888
$endgroup$
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.)
answered Nov 15 '18 at 1:20
Chris CulterChris Culter
21.5k43888
answered Nov 15 '18 at 1:20
Chris CulterChris Culter
21.5k43888
answered Nov 15 '18 at 1:20
Chris CulterChris Culter
21.5k43888
answered Nov 15 '18 at 1:20
Chris CulterChris Culter
21.5k43888
21.5k43888
$begingroup$
That looks like an answer, that does. I'll scrutinise it ... but it has a solid look about it.
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:27
$begingroup$
Oh ... thankyou, by the way!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:28
$begingroup$
You're welcome!
$endgroup$
– Chris Culter
Nov 15 '18 at 21:18
add a comment |
$begingroup$
That looks like an answer, that does. I'll scrutinise it ... but it has a solid look about it.
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:27
$begingroup$
Oh ... thankyou, by the way!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:28
$begingroup$
You're welcome!
$endgroup$
– Chris Culter
Nov 15 '18 at 21:18
$begingroup$
That looks like an answer, that does. I'll scrutinise it ... but it has a solid look about it.
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:27
$begingroup$
That looks like an answer, that does. I'll scrutinise it ... but it has a solid look about it.
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:27
$begingroup$
Oh ... thankyou, by the way!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:28
$begingroup$
Oh ... thankyou, by the way!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:28
$begingroup$
You're welcome!
$endgroup$
– Chris Culter
Nov 15 '18 at 21:18
$begingroup$
You're welcome!
$endgroup$
– Chris Culter
Nov 15 '18 at 21:18
add a comment |
$begingroup$
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.
answered Nov 15 '18 at 1:21
Ross MillikanRoss Millikan
301k24200375
$endgroup$
$begingroup$
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!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:30
$begingroup$
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.
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:37
add a comment |
$begingroup$
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.
answered Nov 15 '18 at 1:21
Ross MillikanRoss Millikan
301k24200375
$endgroup$
$begingroup$
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!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:30
$begingroup$
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.
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:37
add a comment |
$begingroup$
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.
answered Nov 15 '18 at 1:21
Ross MillikanRoss Millikan
301k24200375
$endgroup$
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.
answered Nov 15 '18 at 1:21
Ross MillikanRoss Millikan
301k24200375
answered Nov 15 '18 at 1:21
Ross MillikanRoss Millikan
301k24200375
answered Nov 15 '18 at 1:21
Ross MillikanRoss Millikan
301k24200375
answered Nov 15 '18 at 1:21
Ross MillikanRoss Millikan
301k24200375
301k24200375
$begingroup$
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!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:30
$begingroup$
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.
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:37
add a comment |
$begingroup$
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!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:30
$begingroup$
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.
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:37
$begingroup$
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!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:30
$begingroup$
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!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:30
$begingroup$
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.
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:37
$begingroup$
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.
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 1:37
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2999019%2fsum-of-itemwise-products-of-two-sets-of-real-numbers%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
Rearrangement inequality?
$endgroup$
– lastresort
Nov 15 '18 at 6:10
$begingroup$
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!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 6:27
$begingroup$
Seen it now - thanks for that. And you don't even need the >1 condition!
$endgroup$
– AmbretteOrrisey
Nov 15 '18 at 6:30