Inductive proof verification
$begingroup$
Prove that $x^n>1$ using induction given that $x>1$.
Here was my way of (maybe) proving it:
Step 1: $x^1>1$ which is true going back to what is given.
Step 2: Assume $x^k>1$
Step 3: Prove $x^{k+1}>1$ (If someone could show me how to properly format exponents with operations in them please do so).
$x^{k+1}=xcdot x^k>1 cdot k$
$x cdot x^k>1 cdot k rightarrow x^k>1$
So because I got back to the fact that $x^k>1$, and showed that $x^{k+1}$ is equal to it, am I done?
proof-verification proof-writing induction
$endgroup$
add a comment |
$begingroup$
Prove that $x^n>1$ using induction given that $x>1$.
Here was my way of (maybe) proving it:
Step 1: $x^1>1$ which is true going back to what is given.
Step 2: Assume $x^k>1$
Step 3: Prove $x^{k+1}>1$ (If someone could show me how to properly format exponents with operations in them please do so).
$x^{k+1}=xcdot x^k>1 cdot k$
$x cdot x^k>1 cdot k rightarrow x^k>1$
So because I got back to the fact that $x^k>1$, and showed that $x^{k+1}$ is equal to it, am I done?
proof-verification proof-writing induction
$endgroup$
1
$begingroup$
You are close, but your logic is a bit off. Induction requires (i) proving for some base case (which you have done), (ii) supposing your statement is true for $n=k$, and then (iii) proving the statement is true for $n= k+1$. So you should be wanting to show $x^{k+1} > 1$ rather than 'getting back to the fact that $x^k > 1$'.
$endgroup$
– T. Fo
Dec 29 '18 at 3:47
$begingroup$
How do you get that $xcdot x^k > 1 cdot k$? That isn't nescessarily true. (So $x = 1.00001$ and $k = 3$ then $x^4 not >3$.) But You should have $xcdot x^k > 1cdot x^k$. And as $x^k > 1$ we have $x^{k+1} > x^k > 1$.
$endgroup$
– fleablood
Dec 29 '18 at 4:06
1
$begingroup$
..... in fact informally you should have $1 < x < x^2 < x^3 <...... < x^k < x^{k+1}$. That may informal and and novice student might think it is "childish" and can't be correct. But it is correct, and that IS the thinking the induction is supposed to evoke.
$endgroup$
– fleablood
Dec 29 '18 at 4:10
add a comment |
$begingroup$
Prove that $x^n>1$ using induction given that $x>1$.
Here was my way of (maybe) proving it:
Step 1: $x^1>1$ which is true going back to what is given.
Step 2: Assume $x^k>1$
Step 3: Prove $x^{k+1}>1$ (If someone could show me how to properly format exponents with operations in them please do so).
$x^{k+1}=xcdot x^k>1 cdot k$
$x cdot x^k>1 cdot k rightarrow x^k>1$
So because I got back to the fact that $x^k>1$, and showed that $x^{k+1}$ is equal to it, am I done?
proof-verification proof-writing induction
$endgroup$
Prove that $x^n>1$ using induction given that $x>1$.
Here was my way of (maybe) proving it:
Step 1: $x^1>1$ which is true going back to what is given.
Step 2: Assume $x^k>1$
Step 3: Prove $x^{k+1}>1$ (If someone could show me how to properly format exponents with operations in them please do so).
$x^{k+1}=xcdot x^k>1 cdot k$
$x cdot x^k>1 cdot k rightarrow x^k>1$
So because I got back to the fact that $x^k>1$, and showed that $x^{k+1}$ is equal to it, am I done?
proof-verification proof-writing induction
proof-verification proof-writing induction
edited Dec 29 '18 at 4:09
Bram28
63.8k44793
63.8k44793
asked Dec 29 '18 at 3:37
Jon dueJon due
948
948
1
$begingroup$
You are close, but your logic is a bit off. Induction requires (i) proving for some base case (which you have done), (ii) supposing your statement is true for $n=k$, and then (iii) proving the statement is true for $n= k+1$. So you should be wanting to show $x^{k+1} > 1$ rather than 'getting back to the fact that $x^k > 1$'.
$endgroup$
– T. Fo
Dec 29 '18 at 3:47
$begingroup$
How do you get that $xcdot x^k > 1 cdot k$? That isn't nescessarily true. (So $x = 1.00001$ and $k = 3$ then $x^4 not >3$.) But You should have $xcdot x^k > 1cdot x^k$. And as $x^k > 1$ we have $x^{k+1} > x^k > 1$.
$endgroup$
– fleablood
Dec 29 '18 at 4:06
1
$begingroup$
..... in fact informally you should have $1 < x < x^2 < x^3 <...... < x^k < x^{k+1}$. That may informal and and novice student might think it is "childish" and can't be correct. But it is correct, and that IS the thinking the induction is supposed to evoke.
$endgroup$
– fleablood
Dec 29 '18 at 4:10
add a comment |
1
$begingroup$
You are close, but your logic is a bit off. Induction requires (i) proving for some base case (which you have done), (ii) supposing your statement is true for $n=k$, and then (iii) proving the statement is true for $n= k+1$. So you should be wanting to show $x^{k+1} > 1$ rather than 'getting back to the fact that $x^k > 1$'.
$endgroup$
– T. Fo
Dec 29 '18 at 3:47
$begingroup$
How do you get that $xcdot x^k > 1 cdot k$? That isn't nescessarily true. (So $x = 1.00001$ and $k = 3$ then $x^4 not >3$.) But You should have $xcdot x^k > 1cdot x^k$. And as $x^k > 1$ we have $x^{k+1} > x^k > 1$.
$endgroup$
– fleablood
Dec 29 '18 at 4:06
1
$begingroup$
..... in fact informally you should have $1 < x < x^2 < x^3 <...... < x^k < x^{k+1}$. That may informal and and novice student might think it is "childish" and can't be correct. But it is correct, and that IS the thinking the induction is supposed to evoke.
$endgroup$
– fleablood
Dec 29 '18 at 4:10
1
1
$begingroup$
You are close, but your logic is a bit off. Induction requires (i) proving for some base case (which you have done), (ii) supposing your statement is true for $n=k$, and then (iii) proving the statement is true for $n= k+1$. So you should be wanting to show $x^{k+1} > 1$ rather than 'getting back to the fact that $x^k > 1$'.
$endgroup$
– T. Fo
Dec 29 '18 at 3:47
$begingroup$
You are close, but your logic is a bit off. Induction requires (i) proving for some base case (which you have done), (ii) supposing your statement is true for $n=k$, and then (iii) proving the statement is true for $n= k+1$. So you should be wanting to show $x^{k+1} > 1$ rather than 'getting back to the fact that $x^k > 1$'.
$endgroup$
– T. Fo
Dec 29 '18 at 3:47
$begingroup$
How do you get that $xcdot x^k > 1 cdot k$? That isn't nescessarily true. (So $x = 1.00001$ and $k = 3$ then $x^4 not >3$.) But You should have $xcdot x^k > 1cdot x^k$. And as $x^k > 1$ we have $x^{k+1} > x^k > 1$.
$endgroup$
– fleablood
Dec 29 '18 at 4:06
$begingroup$
How do you get that $xcdot x^k > 1 cdot k$? That isn't nescessarily true. (So $x = 1.00001$ and $k = 3$ then $x^4 not >3$.) But You should have $xcdot x^k > 1cdot x^k$. And as $x^k > 1$ we have $x^{k+1} > x^k > 1$.
$endgroup$
– fleablood
Dec 29 '18 at 4:06
1
1
$begingroup$
..... in fact informally you should have $1 < x < x^2 < x^3 <...... < x^k < x^{k+1}$. That may informal and and novice student might think it is "childish" and can't be correct. But it is correct, and that IS the thinking the induction is supposed to evoke.
$endgroup$
– fleablood
Dec 29 '18 at 4:10
$begingroup$
..... in fact informally you should have $1 < x < x^2 < x^3 <...... < x^k < x^{k+1}$. That may informal and and novice student might think it is "childish" and can't be correct. But it is correct, and that IS the thinking the induction is supposed to evoke.
$endgroup$
– fleablood
Dec 29 '18 at 4:10
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
This is not right. First, what is the $k$ doing in the $1 * k$ term?
Second, and much, much, more importantly, you are going the wrong way around. You are effectively trying to go from $x^{k+1}>1$ to $x^k >1$, but you need to go just the other way around: you need to show that if $x^k>1$, then $x^{k+1}>1$
This is a very common mistake that people make with induction proofs. They start with what needs to be shown, and then show that what follows from that is something is true. Often the proof ends with some trivially true statement like $1=1$ or, as in your case, the inductive hypothesis.
However, notice that showing this shows absolutely nothing: of course $1=1$! So? Does the fact that some statement $P$ implies $1=1$ mean that statement $P$ is true? No, because you can derive $1=1$ from any statement, including false ones.
Likewise, if you assume that $x^k>1$, and then show that $x^{k+1}>1$ implies that $x^k>1$, you havent't shown that $x^{k+1}>1$ at all: once you assumed $x^k>1$, any statement implies $x^k>1$, and so in fact nothing can be concluded about the truth of $x^{k+1}>1$
$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%2f3055510%2finductive-proof-verification%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$
This is not right. First, what is the $k$ doing in the $1 * k$ term?
Second, and much, much, more importantly, you are going the wrong way around. You are effectively trying to go from $x^{k+1}>1$ to $x^k >1$, but you need to go just the other way around: you need to show that if $x^k>1$, then $x^{k+1}>1$
This is a very common mistake that people make with induction proofs. They start with what needs to be shown, and then show that what follows from that is something is true. Often the proof ends with some trivially true statement like $1=1$ or, as in your case, the inductive hypothesis.
However, notice that showing this shows absolutely nothing: of course $1=1$! So? Does the fact that some statement $P$ implies $1=1$ mean that statement $P$ is true? No, because you can derive $1=1$ from any statement, including false ones.
Likewise, if you assume that $x^k>1$, and then show that $x^{k+1}>1$ implies that $x^k>1$, you havent't shown that $x^{k+1}>1$ at all: once you assumed $x^k>1$, any statement implies $x^k>1$, and so in fact nothing can be concluded about the truth of $x^{k+1}>1$
$endgroup$
add a comment |
$begingroup$
This is not right. First, what is the $k$ doing in the $1 * k$ term?
Second, and much, much, more importantly, you are going the wrong way around. You are effectively trying to go from $x^{k+1}>1$ to $x^k >1$, but you need to go just the other way around: you need to show that if $x^k>1$, then $x^{k+1}>1$
This is a very common mistake that people make with induction proofs. They start with what needs to be shown, and then show that what follows from that is something is true. Often the proof ends with some trivially true statement like $1=1$ or, as in your case, the inductive hypothesis.
However, notice that showing this shows absolutely nothing: of course $1=1$! So? Does the fact that some statement $P$ implies $1=1$ mean that statement $P$ is true? No, because you can derive $1=1$ from any statement, including false ones.
Likewise, if you assume that $x^k>1$, and then show that $x^{k+1}>1$ implies that $x^k>1$, you havent't shown that $x^{k+1}>1$ at all: once you assumed $x^k>1$, any statement implies $x^k>1$, and so in fact nothing can be concluded about the truth of $x^{k+1}>1$
$endgroup$
add a comment |
$begingroup$
This is not right. First, what is the $k$ doing in the $1 * k$ term?
Second, and much, much, more importantly, you are going the wrong way around. You are effectively trying to go from $x^{k+1}>1$ to $x^k >1$, but you need to go just the other way around: you need to show that if $x^k>1$, then $x^{k+1}>1$
This is a very common mistake that people make with induction proofs. They start with what needs to be shown, and then show that what follows from that is something is true. Often the proof ends with some trivially true statement like $1=1$ or, as in your case, the inductive hypothesis.
However, notice that showing this shows absolutely nothing: of course $1=1$! So? Does the fact that some statement $P$ implies $1=1$ mean that statement $P$ is true? No, because you can derive $1=1$ from any statement, including false ones.
Likewise, if you assume that $x^k>1$, and then show that $x^{k+1}>1$ implies that $x^k>1$, you havent't shown that $x^{k+1}>1$ at all: once you assumed $x^k>1$, any statement implies $x^k>1$, and so in fact nothing can be concluded about the truth of $x^{k+1}>1$
$endgroup$
This is not right. First, what is the $k$ doing in the $1 * k$ term?
Second, and much, much, more importantly, you are going the wrong way around. You are effectively trying to go from $x^{k+1}>1$ to $x^k >1$, but you need to go just the other way around: you need to show that if $x^k>1$, then $x^{k+1}>1$
This is a very common mistake that people make with induction proofs. They start with what needs to be shown, and then show that what follows from that is something is true. Often the proof ends with some trivially true statement like $1=1$ or, as in your case, the inductive hypothesis.
However, notice that showing this shows absolutely nothing: of course $1=1$! So? Does the fact that some statement $P$ implies $1=1$ mean that statement $P$ is true? No, because you can derive $1=1$ from any statement, including false ones.
Likewise, if you assume that $x^k>1$, and then show that $x^{k+1}>1$ implies that $x^k>1$, you havent't shown that $x^{k+1}>1$ at all: once you assumed $x^k>1$, any statement implies $x^k>1$, and so in fact nothing can be concluded about the truth of $x^{k+1}>1$
edited Dec 29 '18 at 4:07
answered Dec 29 '18 at 3:58
Bram28Bram28
63.8k44793
63.8k44793
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%2f3055510%2finductive-proof-verification%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
1
$begingroup$
You are close, but your logic is a bit off. Induction requires (i) proving for some base case (which you have done), (ii) supposing your statement is true for $n=k$, and then (iii) proving the statement is true for $n= k+1$. So you should be wanting to show $x^{k+1} > 1$ rather than 'getting back to the fact that $x^k > 1$'.
$endgroup$
– T. Fo
Dec 29 '18 at 3:47
$begingroup$
How do you get that $xcdot x^k > 1 cdot k$? That isn't nescessarily true. (So $x = 1.00001$ and $k = 3$ then $x^4 not >3$.) But You should have $xcdot x^k > 1cdot x^k$. And as $x^k > 1$ we have $x^{k+1} > x^k > 1$.
$endgroup$
– fleablood
Dec 29 '18 at 4:06
1
$begingroup$
..... in fact informally you should have $1 < x < x^2 < x^3 <...... < x^k < x^{k+1}$. That may informal and and novice student might think it is "childish" and can't be correct. But it is correct, and that IS the thinking the induction is supposed to evoke.
$endgroup$
– fleablood
Dec 29 '18 at 4:10