Why is there a $m-1$ when approximating a lower bound of a function through summation or integral?
$begingroup$
For a monotonically increasing f(x), why does the summation below, on the left hand side, always approximate the lower bound of the summation on the right hand side?
$int_{k=m-1}^n f(k) leq sum_{k=m}^n f(k)$
If $f(x)=k$, $m=2$, and for $ngeq 2$ then the left hand summation is no longer a lower bound, which contradicts the above.
This formula sheet from a class suggests the left hand side would be a lower bound: https://www.cs.umd.edu/class/fall2018/cmsc351-01XX02XX/files/info.pdf
EDIT: I understand that I'm going wrong somewhere but I don't know where. The purpose of my comments is to demonstrate my reasoning for why I think there's a contradiction so that others can point out where my reasoning is incorrect. Thanks
EDIT 2: I've changed the summation symbol to an integral symbol to avoid confusion. It's worth nothing the results would be the same since the functions are called on integers (discrete intervals).
EDIT 3: The result is not the same with the change from a summation to integral because the $n$ on the left hand side is not included in the summation (so same as summation $m-1$ to $n-1$). Thanks Ross!
calculus functions summation upper-lower-bounds
asked Dec 30 '18 at 14:48
Omkar KonaraddiOmkar Konaraddi
42
$endgroup$
add a comment |
$begingroup$
For a monotonically increasing f(x), why does the summation below, on the left hand side, always approximate the lower bound of the summation on the right hand side?
$int_{k=m-1}^n f(k) leq sum_{k=m}^n f(k)$
If $f(x)=k$, $m=2$, and for $ngeq 2$ then the left hand summation is no longer a lower bound, which contradicts the above.
This formula sheet from a class suggests the left hand side would be a lower bound: https://www.cs.umd.edu/class/fall2018/cmsc351-01XX02XX/files/info.pdf
EDIT: I understand that I'm going wrong somewhere but I don't know where. The purpose of my comments is to demonstrate my reasoning for why I think there's a contradiction so that others can point out where my reasoning is incorrect. Thanks
EDIT 2: I've changed the summation symbol to an integral symbol to avoid confusion. It's worth nothing the results would be the same since the functions are called on integers (discrete intervals).
EDIT 3: The result is not the same with the change from a summation to integral because the $n$ on the left hand side is not included in the summation (so same as summation $m-1$ to $n-1$). Thanks Ross!
calculus functions summation upper-lower-bounds
asked Dec 30 '18 at 14:48
Omkar KonaraddiOmkar Konaraddi
42
$endgroup$
$begingroup$
Wouldn't the left hand side with $f(x)=k$ be $(n-(m-1))k=(n-m+1)k$ and the right hand side be $(n-m)k$? EDIT: The comment I was responding to got deleted.
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:03
$begingroup$
Your latest edit has made my answer inappropriate. The original version had two sums. Now there is not a left hand sum for my comments to apply to. The statement you now make is correct for $f$ increasing as the Riemann sum takes the right side of each interval.
$endgroup$
– Ross Millikan
Dec 30 '18 at 19:37
$begingroup$
I've understood my mistake, thank you!
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 20:28
add a comment |
$begingroup$
For a monotonically increasing f(x), why does the summation below, on the left hand side, always approximate the lower bound of the summation on the right hand side?
$int_{k=m-1}^n f(k) leq sum_{k=m}^n f(k)$
If $f(x)=k$, $m=2$, and for $ngeq 2$ then the left hand summation is no longer a lower bound, which contradicts the above.
This formula sheet from a class suggests the left hand side would be a lower bound: https://www.cs.umd.edu/class/fall2018/cmsc351-01XX02XX/files/info.pdf
EDIT: I understand that I'm going wrong somewhere but I don't know where. The purpose of my comments is to demonstrate my reasoning for why I think there's a contradiction so that others can point out where my reasoning is incorrect. Thanks
EDIT 2: I've changed the summation symbol to an integral symbol to avoid confusion. It's worth nothing the results would be the same since the functions are called on integers (discrete intervals).
EDIT 3: The result is not the same with the change from a summation to integral because the $n$ on the left hand side is not included in the summation (so same as summation $m-1$ to $n-1$). Thanks Ross!
calculus functions summation upper-lower-bounds
asked Dec 30 '18 at 14:48
Omkar KonaraddiOmkar Konaraddi
42
$endgroup$
For a monotonically increasing f(x), why does the summation below, on the left hand side, always approximate the lower bound of the summation on the right hand side?
$int_{k=m-1}^n f(k) leq sum_{k=m}^n f(k)$
If $f(x)=k$, $m=2$, and for $ngeq 2$ then the left hand summation is no longer a lower bound, which contradicts the above.
This formula sheet from a class suggests the left hand side would be a lower bound: https://www.cs.umd.edu/class/fall2018/cmsc351-01XX02XX/files/info.pdf
EDIT: I understand that I'm going wrong somewhere but I don't know where. The purpose of my comments is to demonstrate my reasoning for why I think there's a contradiction so that others can point out where my reasoning is incorrect. Thanks
EDIT 2: I've changed the summation symbol to an integral symbol to avoid confusion. It's worth nothing the results would be the same since the functions are called on integers (discrete intervals).
EDIT 3: The result is not the same with the change from a summation to integral because the $n$ on the left hand side is not included in the summation (so same as summation $m-1$ to $n-1$). Thanks Ross!
calculus functions summation upper-lower-bounds
calculus functions summation upper-lower-bounds
asked Dec 30 '18 at 14:48
Omkar KonaraddiOmkar Konaraddi
42
asked Dec 30 '18 at 14:48
Omkar KonaraddiOmkar Konaraddi
42
edited Dec 30 '18 at 20:30
Omkar Konaraddi
asked Dec 30 '18 at 14:48
Omkar KonaraddiOmkar Konaraddi
42
asked Dec 30 '18 at 14:48
Omkar KonaraddiOmkar Konaraddi
42
asked Dec 30 '18 at 14:48
Omkar KonaraddiOmkar Konaraddi
42
42
$begingroup$
Wouldn't the left hand side with $f(x)=k$ be $(n-(m-1))k=(n-m+1)k$ and the right hand side be $(n-m)k$? EDIT: The comment I was responding to got deleted.
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:03
$begingroup$
Your latest edit has made my answer inappropriate. The original version had two sums. Now there is not a left hand sum for my comments to apply to. The statement you now make is correct for $f$ increasing as the Riemann sum takes the right side of each interval.
$endgroup$
– Ross Millikan
Dec 30 '18 at 19:37
$begingroup$
I've understood my mistake, thank you!
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 20:28
add a comment |
$begingroup$
Wouldn't the left hand side with $f(x)=k$ be $(n-(m-1))k=(n-m+1)k$ and the right hand side be $(n-m)k$? EDIT: The comment I was responding to got deleted.
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:03
$begingroup$
Your latest edit has made my answer inappropriate. The original version had two sums. Now there is not a left hand sum for my comments to apply to. The statement you now make is correct for $f$ increasing as the Riemann sum takes the right side of each interval.
$endgroup$
– Ross Millikan
Dec 30 '18 at 19:37
$begingroup$
I've understood my mistake, thank you!
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 20:28
$begingroup$
Wouldn't the left hand side with $f(x)=k$ be $(n-(m-1))k=(n-m+1)k$ and the right hand side be $(n-m)k$? EDIT: The comment I was responding to got deleted.
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:03
$begingroup$
Wouldn't the left hand side with $f(x)=k$ be $(n-(m-1))k=(n-m+1)k$ and the right hand side be $(n-m)k$? EDIT: The comment I was responding to got deleted.
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:03
$begingroup$
Your latest edit has made my answer inappropriate. The original version had two sums. Now there is not a left hand sum for my comments to apply to. The statement you now make is correct for $f$ increasing as the Riemann sum takes the right side of each interval.
$endgroup$
– Ross Millikan
Dec 30 '18 at 19:37
$begingroup$
Your latest edit has made my answer inappropriate. The original version had two sums. Now there is not a left hand sum for my comments to apply to. The statement you now make is correct for $f$ increasing as the Riemann sum takes the right side of each interval.
$endgroup$
– Ross Millikan
Dec 30 '18 at 19:37
$begingroup$
I've understood my mistake, thank you!
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 20:28
$begingroup$
I've understood my mistake, thank you!
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 20:28
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The upper limit on the left should be $n-1$. The integral you are approximating is from $m-1$ to $n$. You have ends and break points at $m-1,m,m+1,m+2ldots n-1,n$. Using the left side takes the value of $f(x)$ from the left hand end of each interval while the right side takes the value of $f(x)$ from the right hand side of each interval. As $f(x)$ is increasing, the right side will be larger. The true integral will be between the two values.
Your formula sheet gives for $f(x)$ increasing
$$int_{m-1}^nf(x)dx le sum_{k=m}^nf(k)le int_{m}^{n+1}f(x)dx$$
When you try to bound the left integral by a sum you need to make the limits on the integral match. If you shift the limits on the right integral down by $1$ you get the left integral. The lower bound sum then has to have both its limits decreased by $1$, giving the correct formula
$$sum_{k=m-1}^{n-1}f(k) le int_{m-1}^nf(x)dx le sum_{k=m}^nf(k)$$
This shows the upper limit on the left sum should be $n-1$. The easiest way to see the problem is to use $f(x)=1$. Your left sum is then $n-m+1$ and your right sum is $n-m$. The integral is also $n-m$. You are adding one too many terms on the left.
answered Dec 30 '18 at 14:54
Ross MillikanRoss Millikan
300k24200375
$endgroup$
$begingroup$
This contradicts the formula sheet here: cs.umd.edu/class/fall2018/cmsc351-01XX02XX/files/info.pdf and here: staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap03.htm (CTRL + F "approximation by integrals". Both use $m-1$ for the lower bound and do not use $n-1$ for the upper bound.
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:00
$begingroup$
You want to sum the same number of terms on both sides. I have usually seen the right starting at $m$ going to $n-1$ and the left starting at $m+1$ going to $n$. The logic is the same. Just take $f(x)=1$ to see that you need the number of terms to match.
$endgroup$
– Ross Millikan
Dec 30 '18 at 15:07
$begingroup$
The formula sheet you linked in the question has the sum bounded by integrals, but the idea is the same. The range of the integrals is $n-m+1$ and the number of terms in the sum is $n-m+1$
$endgroup$
– Ross Millikan
Dec 30 '18 at 15:10
$begingroup$
How is the number of terms the same if one side is going from $m-1$ to $n$ and the other side is going from $m$ to $n$? The left hand side has 1 more term in addition to all the terms of the right hand side. Thus, the left hand side must be larger whenever $m geq 2$ and $n geq 2$.
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:26
$begingroup$
For example, if $f(x)=x$, $m=2$ and $n=3$ then $sum_{x=1}^{3} x leq sum_{x=2}^{3} x $ does not hold true (because 1 + 2 + 3 is greater than 2 + 3)
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:29
|
show 5 more comments
Your Answer
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%2f3056889%2fwhy-is-there-a-m-1-when-approximating-a-lower-bound-of-a-function-through-summ%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The upper limit on the left should be $n-1$. The integral you are approximating is from $m-1$ to $n$. You have ends and break points at $m-1,m,m+1,m+2ldots n-1,n$. Using the left side takes the value of $f(x)$ from the left hand end of each interval while the right side takes the value of $f(x)$ from the right hand side of each interval. As $f(x)$ is increasing, the right side will be larger. The true integral will be between the two values.
Your formula sheet gives for $f(x)$ increasing
$$int_{m-1}^nf(x)dx le sum_{k=m}^nf(k)le int_{m}^{n+1}f(x)dx$$
When you try to bound the left integral by a sum you need to make the limits on the integral match. If you shift the limits on the right integral down by $1$ you get the left integral. The lower bound sum then has to have both its limits decreased by $1$, giving the correct formula
$$sum_{k=m-1}^{n-1}f(k) le int_{m-1}^nf(x)dx le sum_{k=m}^nf(k)$$
This shows the upper limit on the left sum should be $n-1$. The easiest way to see the problem is to use $f(x)=1$. Your left sum is then $n-m+1$ and your right sum is $n-m$. The integral is also $n-m$. You are adding one too many terms on the left.
answered Dec 30 '18 at 14:54
Ross MillikanRoss Millikan
300k24200375
$endgroup$
$begingroup$
This contradicts the formula sheet here: cs.umd.edu/class/fall2018/cmsc351-01XX02XX/files/info.pdf and here: staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap03.htm (CTRL + F "approximation by integrals". Both use $m-1$ for the lower bound and do not use $n-1$ for the upper bound.
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:00
$begingroup$
You want to sum the same number of terms on both sides. I have usually seen the right starting at $m$ going to $n-1$ and the left starting at $m+1$ going to $n$. The logic is the same. Just take $f(x)=1$ to see that you need the number of terms to match.
$endgroup$
– Ross Millikan
Dec 30 '18 at 15:07
$begingroup$
The formula sheet you linked in the question has the sum bounded by integrals, but the idea is the same. The range of the integrals is $n-m+1$ and the number of terms in the sum is $n-m+1$
$endgroup$
– Ross Millikan
Dec 30 '18 at 15:10
$begingroup$
How is the number of terms the same if one side is going from $m-1$ to $n$ and the other side is going from $m$ to $n$? The left hand side has 1 more term in addition to all the terms of the right hand side. Thus, the left hand side must be larger whenever $m geq 2$ and $n geq 2$.
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:26
$begingroup$
For example, if $f(x)=x$, $m=2$ and $n=3$ then $sum_{x=1}^{3} x leq sum_{x=2}^{3} x $ does not hold true (because 1 + 2 + 3 is greater than 2 + 3)
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:29
|
show 5 more comments
$begingroup$
The upper limit on the left should be $n-1$. The integral you are approximating is from $m-1$ to $n$. You have ends and break points at $m-1,m,m+1,m+2ldots n-1,n$. Using the left side takes the value of $f(x)$ from the left hand end of each interval while the right side takes the value of $f(x)$ from the right hand side of each interval. As $f(x)$ is increasing, the right side will be larger. The true integral will be between the two values.
Your formula sheet gives for $f(x)$ increasing
$$int_{m-1}^nf(x)dx le sum_{k=m}^nf(k)le int_{m}^{n+1}f(x)dx$$
When you try to bound the left integral by a sum you need to make the limits on the integral match. If you shift the limits on the right integral down by $1$ you get the left integral. The lower bound sum then has to have both its limits decreased by $1$, giving the correct formula
$$sum_{k=m-1}^{n-1}f(k) le int_{m-1}^nf(x)dx le sum_{k=m}^nf(k)$$
This shows the upper limit on the left sum should be $n-1$. The easiest way to see the problem is to use $f(x)=1$. Your left sum is then $n-m+1$ and your right sum is $n-m$. The integral is also $n-m$. You are adding one too many terms on the left.
answered Dec 30 '18 at 14:54
Ross MillikanRoss Millikan
300k24200375
$endgroup$
$begingroup$
This contradicts the formula sheet here: cs.umd.edu/class/fall2018/cmsc351-01XX02XX/files/info.pdf and here: staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap03.htm (CTRL + F "approximation by integrals". Both use $m-1$ for the lower bound and do not use $n-1$ for the upper bound.
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:00
$begingroup$
You want to sum the same number of terms on both sides. I have usually seen the right starting at $m$ going to $n-1$ and the left starting at $m+1$ going to $n$. The logic is the same. Just take $f(x)=1$ to see that you need the number of terms to match.
$endgroup$
– Ross Millikan
Dec 30 '18 at 15:07
$begingroup$
The formula sheet you linked in the question has the sum bounded by integrals, but the idea is the same. The range of the integrals is $n-m+1$ and the number of terms in the sum is $n-m+1$
$endgroup$
– Ross Millikan
Dec 30 '18 at 15:10
$begingroup$
How is the number of terms the same if one side is going from $m-1$ to $n$ and the other side is going from $m$ to $n$? The left hand side has 1 more term in addition to all the terms of the right hand side. Thus, the left hand side must be larger whenever $m geq 2$ and $n geq 2$.
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:26
$begingroup$
For example, if $f(x)=x$, $m=2$ and $n=3$ then $sum_{x=1}^{3} x leq sum_{x=2}^{3} x $ does not hold true (because 1 + 2 + 3 is greater than 2 + 3)
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:29
|
show 5 more comments
$begingroup$
The upper limit on the left should be $n-1$. The integral you are approximating is from $m-1$ to $n$. You have ends and break points at $m-1,m,m+1,m+2ldots n-1,n$. Using the left side takes the value of $f(x)$ from the left hand end of each interval while the right side takes the value of $f(x)$ from the right hand side of each interval. As $f(x)$ is increasing, the right side will be larger. The true integral will be between the two values.
Your formula sheet gives for $f(x)$ increasing
$$int_{m-1}^nf(x)dx le sum_{k=m}^nf(k)le int_{m}^{n+1}f(x)dx$$
When you try to bound the left integral by a sum you need to make the limits on the integral match. If you shift the limits on the right integral down by $1$ you get the left integral. The lower bound sum then has to have both its limits decreased by $1$, giving the correct formula
$$sum_{k=m-1}^{n-1}f(k) le int_{m-1}^nf(x)dx le sum_{k=m}^nf(k)$$
This shows the upper limit on the left sum should be $n-1$. The easiest way to see the problem is to use $f(x)=1$. Your left sum is then $n-m+1$ and your right sum is $n-m$. The integral is also $n-m$. You are adding one too many terms on the left.
answered Dec 30 '18 at 14:54
Ross MillikanRoss Millikan
300k24200375
$endgroup$
The upper limit on the left should be $n-1$. The integral you are approximating is from $m-1$ to $n$. You have ends and break points at $m-1,m,m+1,m+2ldots n-1,n$. Using the left side takes the value of $f(x)$ from the left hand end of each interval while the right side takes the value of $f(x)$ from the right hand side of each interval. As $f(x)$ is increasing, the right side will be larger. The true integral will be between the two values.
Your formula sheet gives for $f(x)$ increasing
$$int_{m-1}^nf(x)dx le sum_{k=m}^nf(k)le int_{m}^{n+1}f(x)dx$$
When you try to bound the left integral by a sum you need to make the limits on the integral match. If you shift the limits on the right integral down by $1$ you get the left integral. The lower bound sum then has to have both its limits decreased by $1$, giving the correct formula
$$sum_{k=m-1}^{n-1}f(k) le int_{m-1}^nf(x)dx le sum_{k=m}^nf(k)$$
This shows the upper limit on the left sum should be $n-1$. The easiest way to see the problem is to use $f(x)=1$. Your left sum is then $n-m+1$ and your right sum is $n-m$. The integral is also $n-m$. You are adding one too many terms on the left.
answered Dec 30 '18 at 14:54
Ross MillikanRoss Millikan
300k24200375
edited Dec 30 '18 at 19:34
answered Dec 30 '18 at 14:54
Ross MillikanRoss Millikan
300k24200375
answered Dec 30 '18 at 14:54
Ross MillikanRoss Millikan
300k24200375
answered Dec 30 '18 at 14:54
Ross MillikanRoss Millikan
300k24200375
300k24200375
$begingroup$
This contradicts the formula sheet here: cs.umd.edu/class/fall2018/cmsc351-01XX02XX/files/info.pdf and here: staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap03.htm (CTRL + F "approximation by integrals". Both use $m-1$ for the lower bound and do not use $n-1$ for the upper bound.
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:00
$begingroup$
You want to sum the same number of terms on both sides. I have usually seen the right starting at $m$ going to $n-1$ and the left starting at $m+1$ going to $n$. The logic is the same. Just take $f(x)=1$ to see that you need the number of terms to match.
$endgroup$
– Ross Millikan
Dec 30 '18 at 15:07
$begingroup$
The formula sheet you linked in the question has the sum bounded by integrals, but the idea is the same. The range of the integrals is $n-m+1$ and the number of terms in the sum is $n-m+1$
$endgroup$
– Ross Millikan
Dec 30 '18 at 15:10
$begingroup$
How is the number of terms the same if one side is going from $m-1$ to $n$ and the other side is going from $m$ to $n$? The left hand side has 1 more term in addition to all the terms of the right hand side. Thus, the left hand side must be larger whenever $m geq 2$ and $n geq 2$.
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:26
$begingroup$
For example, if $f(x)=x$, $m=2$ and $n=3$ then $sum_{x=1}^{3} x leq sum_{x=2}^{3} x $ does not hold true (because 1 + 2 + 3 is greater than 2 + 3)
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:29
|
show 5 more comments
$begingroup$
This contradicts the formula sheet here: cs.umd.edu/class/fall2018/cmsc351-01XX02XX/files/info.pdf and here: staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap03.htm (CTRL + F "approximation by integrals". Both use $m-1$ for the lower bound and do not use $n-1$ for the upper bound.
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:00
$begingroup$
You want to sum the same number of terms on both sides. I have usually seen the right starting at $m$ going to $n-1$ and the left starting at $m+1$ going to $n$. The logic is the same. Just take $f(x)=1$ to see that you need the number of terms to match.
$endgroup$
– Ross Millikan
Dec 30 '18 at 15:07
$begingroup$
The formula sheet you linked in the question has the sum bounded by integrals, but the idea is the same. The range of the integrals is $n-m+1$ and the number of terms in the sum is $n-m+1$
$endgroup$
– Ross Millikan
Dec 30 '18 at 15:10
$begingroup$
How is the number of terms the same if one side is going from $m-1$ to $n$ and the other side is going from $m$ to $n$? The left hand side has 1 more term in addition to all the terms of the right hand side. Thus, the left hand side must be larger whenever $m geq 2$ and $n geq 2$.
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:26
$begingroup$
For example, if $f(x)=x$, $m=2$ and $n=3$ then $sum_{x=1}^{3} x leq sum_{x=2}^{3} x $ does not hold true (because 1 + 2 + 3 is greater than 2 + 3)
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:29
$begingroup$
This contradicts the formula sheet here: cs.umd.edu/class/fall2018/cmsc351-01XX02XX/files/info.pdf and here: staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap03.htm (CTRL + F "approximation by integrals". Both use $m-1$ for the lower bound and do not use $n-1$ for the upper bound.
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:00
$begingroup$
This contradicts the formula sheet here: cs.umd.edu/class/fall2018/cmsc351-01XX02XX/files/info.pdf and here: staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap03.htm (CTRL + F "approximation by integrals". Both use $m-1$ for the lower bound and do not use $n-1$ for the upper bound.
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:00
$begingroup$
You want to sum the same number of terms on both sides. I have usually seen the right starting at $m$ going to $n-1$ and the left starting at $m+1$ going to $n$. The logic is the same. Just take $f(x)=1$ to see that you need the number of terms to match.
$endgroup$
– Ross Millikan
Dec 30 '18 at 15:07
$begingroup$
You want to sum the same number of terms on both sides. I have usually seen the right starting at $m$ going to $n-1$ and the left starting at $m+1$ going to $n$. The logic is the same. Just take $f(x)=1$ to see that you need the number of terms to match.
$endgroup$
– Ross Millikan
Dec 30 '18 at 15:07
$begingroup$
The formula sheet you linked in the question has the sum bounded by integrals, but the idea is the same. The range of the integrals is $n-m+1$ and the number of terms in the sum is $n-m+1$
$endgroup$
– Ross Millikan
Dec 30 '18 at 15:10
$begingroup$
The formula sheet you linked in the question has the sum bounded by integrals, but the idea is the same. The range of the integrals is $n-m+1$ and the number of terms in the sum is $n-m+1$
$endgroup$
– Ross Millikan
Dec 30 '18 at 15:10
$begingroup$
How is the number of terms the same if one side is going from $m-1$ to $n$ and the other side is going from $m$ to $n$? The left hand side has 1 more term in addition to all the terms of the right hand side. Thus, the left hand side must be larger whenever $m geq 2$ and $n geq 2$.
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:26
$begingroup$
How is the number of terms the same if one side is going from $m-1$ to $n$ and the other side is going from $m$ to $n$? The left hand side has 1 more term in addition to all the terms of the right hand side. Thus, the left hand side must be larger whenever $m geq 2$ and $n geq 2$.
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:26
$begingroup$
For example, if $f(x)=x$, $m=2$ and $n=3$ then $sum_{x=1}^{3} x leq sum_{x=2}^{3} x $ does not hold true (because 1 + 2 + 3 is greater than 2 + 3)
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:29
$begingroup$
For example, if $f(x)=x$, $m=2$ and $n=3$ then $sum_{x=1}^{3} x leq sum_{x=2}^{3} x $ does not hold true (because 1 + 2 + 3 is greater than 2 + 3)
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:29
|
show 5 more comments
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%2f3056889%2fwhy-is-there-a-m-1-when-approximating-a-lower-bound-of-a-function-through-summ%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
$begingroup$
Wouldn't the left hand side with $f(x)=k$ be $(n-(m-1))k=(n-m+1)k$ and the right hand side be $(n-m)k$? EDIT: The comment I was responding to got deleted.
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 15:03
$begingroup$
Your latest edit has made my answer inappropriate. The original version had two sums. Now there is not a left hand sum for my comments to apply to. The statement you now make is correct for $f$ increasing as the Riemann sum takes the right side of each interval.
$endgroup$
– Ross Millikan
Dec 30 '18 at 19:37
$begingroup$
I've understood my mistake, thank you!
$endgroup$
– Omkar Konaraddi
Dec 30 '18 at 20:28