Theorems & Proof Corrections [discrete mathematics]Prove if $n^2$ is even, then $n^2$ is divisible by 4Proof by cases and contradiction. Is this valid?Is this a valid proof? Discrete MathematicsDiscrete Mathematics: Prove Expression Is EvenDiscrete Math (Proof Techniques)Does the following work as a proof for the intermediate value theorum?Confusion proof by contradiction when starting from conclusionThe “assumption” in proof by inductionIndirect Proof [discrete mathematics]Big-$O$ verification [discrete mathematics]
How can I make my BBEG immortal short of making them a Lich or Vampire?
What defenses are there against being summoned by the Gate spell?
Doing something right before you need it - expression for this?
A case of the sniffles
What does the "remote control" for a QF-4 look like?
High voltage LED indicator 40-1000 VDC without additional power supply
How can bays and straits be determined in a procedurally generated map?
Can I make popcorn with any corn?
Paid for article while in US on F-1 visa?
A newer friend of my brother's gave him a load of baseball cards that are supposedly extremely valuable. Is this a scam?
What is the word for reserving something for yourself before others do?
Can a vampire attack twice with their claws using Multiattack?
Character reincarnated...as a snail
When a company launches a new product do they "come out" with a new product or do they "come up" with a new product?
Codimension of non-flat locus
How to determine what difficulty is right for the game?
Is it inappropriate for a student to attend their mentor's dissertation defense?
LaTeX: Why are digits allowed in environments, but forbidden in commands?
Was any UN Security Council vote triple-vetoed?
NMaximize is not converging to a solution
Which country benefited the most from UN Security Council vetoes?
"You are your self first supporter", a more proper way to say it
Languages that we cannot (dis)prove to be Context-Free
Roll the carpet
Theorems & Proof Corrections [discrete mathematics]
Prove if $n^2$ is even, then $n^2$ is divisible by 4Proof by cases and contradiction. Is this valid?Is this a valid proof? Discrete MathematicsDiscrete Mathematics: Prove Expression Is EvenDiscrete Math (Proof Techniques)Does the following work as a proof for the intermediate value theorum?Confusion proof by contradiction when starting from conclusionThe “assumption” in proof by inductionIndirect Proof [discrete mathematics]Big-$O$ verification [discrete mathematics]
$begingroup$
So I've recently started a new chapter in my discrete mathematics course on proof methods. I have come across this problem in my textbook but I'm having a very hard time understanding where to start and what to look for. In all honesty, all the proofs for the theorems look correct to me.
Each of the following theorems is either valid or invalid, but the
proof given is incorrect even if the theorem is valid. Explain briefly
what mistake was made in each case:
Theorem: Let $f$, $g$ and $h$ be three functions from $mathbfN$ into $mathbfR^+$. If $f in O(g)$ and $g in O(h)$,
then $f in O(h)$.
Proof: Consider three unspecified functions $f$, $g$ and $h$ $mathbfN$ into $mathbfR^+$. Assume that $f in O(g)$ and $g in O(h)$. Since $f in O(g)$, there is a real number $c$ and a positive
integer $n_0$ such that for every $n ge n_0$, $f(n) le cg(n)$.
Similarly, for every $n ge n_0$, $g(n) le ch(n)$. Therefore, for
every $n ge n_0$, $f(n) le cg(n) le c(ch(n)) = c^2 h(n)$. Hence
$f in O(h)$ using the constants $c^2$ and $n_0$.
Theorem: If $n^2 + n - 6 ge 0$, then $n ge 2$.
Proof: When $n ge 2$, we know that $n^2 ge 4$, so $n^2 + n ge 6$, and therefore $n^2 + n - 6 ge 0$.
Theorem: No matter how we choose an integer $n$, the value $n^3 + n$ will be even.
Proof: We use a proof by contradiction. Assume that the theorem is false. That is, $n^3 + n$ is odd. This is not true, as
we can see by choosing $n = 2$ ($2^3 + 2 = 10$, which is even). So
we have found a contradiction, which means the theorem is true.
Any help would be greatly appreciated. Thank you!
discrete-mathematics proof-verification proof-writing proof-explanation recreational-mathematics
asked Mar 21 at 18:33
Joe BidenJoe Biden
65
$endgroup$
add a comment |
$begingroup$
So I've recently started a new chapter in my discrete mathematics course on proof methods. I have come across this problem in my textbook but I'm having a very hard time understanding where to start and what to look for. In all honesty, all the proofs for the theorems look correct to me.
Each of the following theorems is either valid or invalid, but the
proof given is incorrect even if the theorem is valid. Explain briefly
what mistake was made in each case:
Theorem: Let $f$, $g$ and $h$ be three functions from $mathbfN$ into $mathbfR^+$. If $f in O(g)$ and $g in O(h)$,
then $f in O(h)$.
Proof: Consider three unspecified functions $f$, $g$ and $h$ $mathbfN$ into $mathbfR^+$. Assume that $f in O(g)$ and $g in O(h)$. Since $f in O(g)$, there is a real number $c$ and a positive
integer $n_0$ such that for every $n ge n_0$, $f(n) le cg(n)$.
Similarly, for every $n ge n_0$, $g(n) le ch(n)$. Therefore, for
every $n ge n_0$, $f(n) le cg(n) le c(ch(n)) = c^2 h(n)$. Hence
$f in O(h)$ using the constants $c^2$ and $n_0$.
Theorem: If $n^2 + n - 6 ge 0$, then $n ge 2$.
Proof: When $n ge 2$, we know that $n^2 ge 4$, so $n^2 + n ge 6$, and therefore $n^2 + n - 6 ge 0$.
Theorem: No matter how we choose an integer $n$, the value $n^3 + n$ will be even.
Proof: We use a proof by contradiction. Assume that the theorem is false. That is, $n^3 + n$ is odd. This is not true, as
we can see by choosing $n = 2$ ($2^3 + 2 = 10$, which is even). So
we have found a contradiction, which means the theorem is true.
Any help would be greatly appreciated. Thank you!
discrete-mathematics proof-verification proof-writing proof-explanation recreational-mathematics
asked Mar 21 at 18:33
Joe BidenJoe Biden
65
$endgroup$
$begingroup$
What is $O(g)$?
$endgroup$
– Robert Shore
Mar 21 at 18:41
1
$begingroup$
For Theorem 2, check out what happens when $n = -100.$ You'll see (I think) that this is a counterexample to the theorem. What happens when you apply the supposed proof to this counterexample? Does that help you see why it's not actually a proof?
$endgroup$
– Robert Shore
Mar 21 at 18:44
$begingroup$
For the second theorem, you're only proving that every $ngeq 2$ satisfies $n^2+n-6geq 0$ but not in the other direction...
$endgroup$
– Dr. Mathva
Mar 21 at 18:46
$begingroup$
For the third theorem, the assumption to be disproved should be $n^3+n$ isn't always even instead of '$n^3+n$ is odd'...
$endgroup$
– Dr. Mathva
Mar 21 at 18:48
add a comment |
$begingroup$
So I've recently started a new chapter in my discrete mathematics course on proof methods. I have come across this problem in my textbook but I'm having a very hard time understanding where to start and what to look for. In all honesty, all the proofs for the theorems look correct to me.
Each of the following theorems is either valid or invalid, but the
proof given is incorrect even if the theorem is valid. Explain briefly
what mistake was made in each case:
Theorem: Let $f$, $g$ and $h$ be three functions from $mathbfN$ into $mathbfR^+$. If $f in O(g)$ and $g in O(h)$,
then $f in O(h)$.
Proof: Consider three unspecified functions $f$, $g$ and $h$ $mathbfN$ into $mathbfR^+$. Assume that $f in O(g)$ and $g in O(h)$. Since $f in O(g)$, there is a real number $c$ and a positive
integer $n_0$ such that for every $n ge n_0$, $f(n) le cg(n)$.
Similarly, for every $n ge n_0$, $g(n) le ch(n)$. Therefore, for
every $n ge n_0$, $f(n) le cg(n) le c(ch(n)) = c^2 h(n)$. Hence
$f in O(h)$ using the constants $c^2$ and $n_0$.
Theorem: If $n^2 + n - 6 ge 0$, then $n ge 2$.
Proof: When $n ge 2$, we know that $n^2 ge 4$, so $n^2 + n ge 6$, and therefore $n^2 + n - 6 ge 0$.
Theorem: No matter how we choose an integer $n$, the value $n^3 + n$ will be even.
Proof: We use a proof by contradiction. Assume that the theorem is false. That is, $n^3 + n$ is odd. This is not true, as
we can see by choosing $n = 2$ ($2^3 + 2 = 10$, which is even). So
we have found a contradiction, which means the theorem is true.
Any help would be greatly appreciated. Thank you!
discrete-mathematics proof-verification proof-writing proof-explanation recreational-mathematics
asked Mar 21 at 18:33
Joe BidenJoe Biden
65
$endgroup$
So I've recently started a new chapter in my discrete mathematics course on proof methods. I have come across this problem in my textbook but I'm having a very hard time understanding where to start and what to look for. In all honesty, all the proofs for the theorems look correct to me.
Each of the following theorems is either valid or invalid, but the
proof given is incorrect even if the theorem is valid. Explain briefly
what mistake was made in each case:
Theorem: Let $f$, $g$ and $h$ be three functions from $mathbfN$ into $mathbfR^+$. If $f in O(g)$ and $g in O(h)$,
then $f in O(h)$.
Proof: Consider three unspecified functions $f$, $g$ and $h$ $mathbfN$ into $mathbfR^+$. Assume that $f in O(g)$ and $g in O(h)$. Since $f in O(g)$, there is a real number $c$ and a positive
integer $n_0$ such that for every $n ge n_0$, $f(n) le cg(n)$.
Similarly, for every $n ge n_0$, $g(n) le ch(n)$. Therefore, for
every $n ge n_0$, $f(n) le cg(n) le c(ch(n)) = c^2 h(n)$. Hence
$f in O(h)$ using the constants $c^2$ and $n_0$.
Theorem: If $n^2 + n - 6 ge 0$, then $n ge 2$.
Proof: When $n ge 2$, we know that $n^2 ge 4$, so $n^2 + n ge 6$, and therefore $n^2 + n - 6 ge 0$.
Theorem: No matter how we choose an integer $n$, the value $n^3 + n$ will be even.
Proof: We use a proof by contradiction. Assume that the theorem is false. That is, $n^3 + n$ is odd. This is not true, as
we can see by choosing $n = 2$ ($2^3 + 2 = 10$, which is even). So
we have found a contradiction, which means the theorem is true.
Any help would be greatly appreciated. Thank you!
discrete-mathematics proof-verification proof-writing proof-explanation recreational-mathematics
discrete-mathematics proof-verification proof-writing proof-explanation recreational-mathematics
asked Mar 21 at 18:33
Joe BidenJoe Biden
65
asked Mar 21 at 18:33
Joe BidenJoe Biden
65
edited Mar 21 at 18:43
Joe Biden
asked Mar 21 at 18:33
Joe BidenJoe Biden
65
asked Mar 21 at 18:33
Joe BidenJoe Biden
65
asked Mar 21 at 18:33
Joe BidenJoe Biden
65
65
$begingroup$
What is $O(g)$?
$endgroup$
– Robert Shore
Mar 21 at 18:41
1
$begingroup$
For Theorem 2, check out what happens when $n = -100.$ You'll see (I think) that this is a counterexample to the theorem. What happens when you apply the supposed proof to this counterexample? Does that help you see why it's not actually a proof?
$endgroup$
– Robert Shore
Mar 21 at 18:44
$begingroup$
For the second theorem, you're only proving that every $ngeq 2$ satisfies $n^2+n-6geq 0$ but not in the other direction...
$endgroup$
– Dr. Mathva
Mar 21 at 18:46
$begingroup$
For the third theorem, the assumption to be disproved should be $n^3+n$ isn't always even instead of '$n^3+n$ is odd'...
$endgroup$
– Dr. Mathva
Mar 21 at 18:48
add a comment |
$begingroup$
What is $O(g)$?
$endgroup$
– Robert Shore
Mar 21 at 18:41
1
$begingroup$
For Theorem 2, check out what happens when $n = -100.$ You'll see (I think) that this is a counterexample to the theorem. What happens when you apply the supposed proof to this counterexample? Does that help you see why it's not actually a proof?
$endgroup$
– Robert Shore
Mar 21 at 18:44
$begingroup$
For the second theorem, you're only proving that every $ngeq 2$ satisfies $n^2+n-6geq 0$ but not in the other direction...
$endgroup$
– Dr. Mathva
Mar 21 at 18:46
$begingroup$
For the third theorem, the assumption to be disproved should be $n^3+n$ isn't always even instead of '$n^3+n$ is odd'...
$endgroup$
– Dr. Mathva
Mar 21 at 18:48
$begingroup$
What is $O(g)$?
$endgroup$
– Robert Shore
Mar 21 at 18:41
$begingroup$
What is $O(g)$?
$endgroup$
– Robert Shore
Mar 21 at 18:41
1
1
$begingroup$
For Theorem 2, check out what happens when $n = -100.$ You'll see (I think) that this is a counterexample to the theorem. What happens when you apply the supposed proof to this counterexample? Does that help you see why it's not actually a proof?
$endgroup$
– Robert Shore
Mar 21 at 18:44
$begingroup$
For Theorem 2, check out what happens when $n = -100.$ You'll see (I think) that this is a counterexample to the theorem. What happens when you apply the supposed proof to this counterexample? Does that help you see why it's not actually a proof?
$endgroup$
– Robert Shore
Mar 21 at 18:44
$begingroup$
For the second theorem, you're only proving that every $ngeq 2$ satisfies $n^2+n-6geq 0$ but not in the other direction...
$endgroup$
– Dr. Mathva
Mar 21 at 18:46
$begingroup$
For the second theorem, you're only proving that every $ngeq 2$ satisfies $n^2+n-6geq 0$ but not in the other direction...
$endgroup$
– Dr. Mathva
Mar 21 at 18:46
$begingroup$
For the third theorem, the assumption to be disproved should be $n^3+n$ isn't always even instead of '$n^3+n$ is odd'...
$endgroup$
– Dr. Mathva
Mar 21 at 18:48
$begingroup$
For the third theorem, the assumption to be disproved should be $n^3+n$ isn't always even instead of '$n^3+n$ is odd'...
$endgroup$
– Dr. Mathva
Mar 21 at 18:48
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Apply the proof of theorem 1 to the particular functions $f(n) = 2, g(n) = n, h(n) = frac n^216$. Find the best $n_0$ and $c$ to show $f in O(g)$, and then check that against the final line of the proof.
For 2, the theorem is $n^2 + n - 6 ge 0 implies n ge 2$. That is, from $n^2 + n - 6 ge 0$, you can prove that $n ge 2$. Is that what their "proof" does?
For 3, here is a very similar proof:
Theorem for all $n$, $n$ is odd.
Proof: Suppose not, then $n$ is even, but that is false, because when $n = 1$, $n$ is not even. A contradiction, so the theorem is true.
Can you spot the error in this version?
answered Mar 22 at 2:27
Paul SinclairPaul Sinclair
20.7k21543
$endgroup$
add a comment |
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%2f3157210%2ftheorems-proof-corrections-discrete-mathematics%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$
Apply the proof of theorem 1 to the particular functions $f(n) = 2, g(n) = n, h(n) = frac n^216$. Find the best $n_0$ and $c$ to show $f in O(g)$, and then check that against the final line of the proof.
For 2, the theorem is $n^2 + n - 6 ge 0 implies n ge 2$. That is, from $n^2 + n - 6 ge 0$, you can prove that $n ge 2$. Is that what their "proof" does?
For 3, here is a very similar proof:
Theorem for all $n$, $n$ is odd.
Proof: Suppose not, then $n$ is even, but that is false, because when $n = 1$, $n$ is not even. A contradiction, so the theorem is true.
Can you spot the error in this version?
answered Mar 22 at 2:27
Paul SinclairPaul Sinclair
20.7k21543
$endgroup$
add a comment |
$begingroup$
Apply the proof of theorem 1 to the particular functions $f(n) = 2, g(n) = n, h(n) = frac n^216$. Find the best $n_0$ and $c$ to show $f in O(g)$, and then check that against the final line of the proof.
For 2, the theorem is $n^2 + n - 6 ge 0 implies n ge 2$. That is, from $n^2 + n - 6 ge 0$, you can prove that $n ge 2$. Is that what their "proof" does?
For 3, here is a very similar proof:
Theorem for all $n$, $n$ is odd.
Proof: Suppose not, then $n$ is even, but that is false, because when $n = 1$, $n$ is not even. A contradiction, so the theorem is true.
Can you spot the error in this version?
answered Mar 22 at 2:27
Paul SinclairPaul Sinclair
20.7k21543
$endgroup$
add a comment |
$begingroup$
Apply the proof of theorem 1 to the particular functions $f(n) = 2, g(n) = n, h(n) = frac n^216$. Find the best $n_0$ and $c$ to show $f in O(g)$, and then check that against the final line of the proof.
For 2, the theorem is $n^2 + n - 6 ge 0 implies n ge 2$. That is, from $n^2 + n - 6 ge 0$, you can prove that $n ge 2$. Is that what their "proof" does?
For 3, here is a very similar proof:
Theorem for all $n$, $n$ is odd.
Proof: Suppose not, then $n$ is even, but that is false, because when $n = 1$, $n$ is not even. A contradiction, so the theorem is true.
Can you spot the error in this version?
answered Mar 22 at 2:27
Paul SinclairPaul Sinclair
20.7k21543
$endgroup$
Apply the proof of theorem 1 to the particular functions $f(n) = 2, g(n) = n, h(n) = frac n^216$. Find the best $n_0$ and $c$ to show $f in O(g)$, and then check that against the final line of the proof.
For 2, the theorem is $n^2 + n - 6 ge 0 implies n ge 2$. That is, from $n^2 + n - 6 ge 0$, you can prove that $n ge 2$. Is that what their "proof" does?
For 3, here is a very similar proof:
Theorem for all $n$, $n$ is odd.
Proof: Suppose not, then $n$ is even, but that is false, because when $n = 1$, $n$ is not even. A contradiction, so the theorem is true.
Can you spot the error in this version?
answered Mar 22 at 2:27
Paul SinclairPaul Sinclair
20.7k21543
answered Mar 22 at 2:27
Paul SinclairPaul Sinclair
20.7k21543
answered Mar 22 at 2:27
Paul SinclairPaul Sinclair
20.7k21543
answered Mar 22 at 2:27
Paul SinclairPaul Sinclair
20.7k21543
20.7k21543
add a comment |
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%2f3157210%2ftheorems-proof-corrections-discrete-mathematics%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$
What is $O(g)$?
$endgroup$
– Robert Shore
Mar 21 at 18:41
1
$begingroup$
For Theorem 2, check out what happens when $n = -100.$ You'll see (I think) that this is a counterexample to the theorem. What happens when you apply the supposed proof to this counterexample? Does that help you see why it's not actually a proof?
$endgroup$
– Robert Shore
Mar 21 at 18:44
$begingroup$
For the second theorem, you're only proving that every $ngeq 2$ satisfies $n^2+n-6geq 0$ but not in the other direction...
$endgroup$
– Dr. Mathva
Mar 21 at 18:46
$begingroup$
For the third theorem, the assumption to be disproved should be $n^3+n$ isn't always even instead of '$n^3+n$ is odd'...
$endgroup$
– Dr. Mathva
Mar 21 at 18:48