Proof by simple induction, question concerning the inductive step
0
$begingroup$
Sorry in advance for posting a picture instead of the text, I'm not familiar with Latex yet...
My question is...
Why do we get:
4n^2 + 12n + 7 = 4((n − 1) + 1)^2 + 12((n − 1) + 1) + 7
And not this:
4n^2 + 12n + 7 = 4(n+1)^2 + 12(n+1) + 7
Proof
induction
asked Jan 7 at 12:14
NortonNorton
113
New contributor
Norton is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
|
show 2 more comments
0
$begingroup$
Sorry in advance for posting a picture instead of the text, I'm not familiar with Latex yet...
My question is...
Why do we get:
4n^2 + 12n + 7 = 4((n − 1) + 1)^2 + 12((n − 1) + 1) + 7
And not this:
4n^2 + 12n + 7 = 4(n+1)^2 + 12(n+1) + 7
Proof
induction
asked Jan 7 at 12:14
NortonNorton
113
New contributor
Norton is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
The first equation is trivially true since $(n-1)+1=n$. The second expression isn't set equal to anything, so I'm not sure what you are asking.
$endgroup$
– lulu
Jan 7 at 12:15
$begingroup$
Sorry I just corrected it - It should just be n instead of k. I originally assumed a fresh witness n = k, but I left it out here to make it more simple.
$endgroup$
– Norton
Jan 7 at 12:16
$begingroup$
I thought that when you add n+1 to 4n^2 it would be 4(n+1)^2, but that is not true I guess?
$endgroup$
– Norton
Jan 7 at 12:18
$begingroup$
The second equation is obviously false. Just take $n=0$ for example.
$endgroup$
– lulu
Jan 7 at 12:20
$begingroup$
Because $n=(n-1)+1$ and $nneq n+1$.
$endgroup$
– drhab
Jan 7 at 12:21
|
show 2 more comments
0
0
0
$begingroup$
Sorry in advance for posting a picture instead of the text, I'm not familiar with Latex yet...
My question is...
Why do we get:
4n^2 + 12n + 7 = 4((n − 1) + 1)^2 + 12((n − 1) + 1) + 7
And not this:
4n^2 + 12n + 7 = 4(n+1)^2 + 12(n+1) + 7
Proof
induction
asked Jan 7 at 12:14
NortonNorton
113
New contributor
Norton is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Sorry in advance for posting a picture instead of the text, I'm not familiar with Latex yet...
My question is...
Why do we get:
4n^2 + 12n + 7 = 4((n − 1) + 1)^2 + 12((n − 1) + 1) + 7
And not this:
4n^2 + 12n + 7 = 4(n+1)^2 + 12(n+1) + 7
Proof
induction
induction
asked Jan 7 at 12:14
NortonNorton
113
New contributor
Norton is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Jan 7 at 12:14
NortonNorton
113
New contributor
Norton is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Jan 7 at 12:17
Norton
asked Jan 7 at 12:14
NortonNorton
113
New contributor
Norton is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Jan 7 at 12:14
NortonNorton
113
asked Jan 7 at 12:14
NortonNorton
113
113
New contributor
Norton is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Norton is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Norton is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$begingroup$
The first equation is trivially true since $(n-1)+1=n$. The second expression isn't set equal to anything, so I'm not sure what you are asking.
$endgroup$
– lulu
Jan 7 at 12:15
$begingroup$
Sorry I just corrected it - It should just be n instead of k. I originally assumed a fresh witness n = k, but I left it out here to make it more simple.
$endgroup$
– Norton
Jan 7 at 12:16
$begingroup$
I thought that when you add n+1 to 4n^2 it would be 4(n+1)^2, but that is not true I guess?
$endgroup$
– Norton
Jan 7 at 12:18
$begingroup$
The second equation is obviously false. Just take $n=0$ for example.
$endgroup$
– lulu
Jan 7 at 12:20
$begingroup$
Because $n=(n-1)+1$ and $nneq n+1$.
$endgroup$
– drhab
Jan 7 at 12:21
|
show 2 more comments
$begingroup$
The first equation is trivially true since $(n-1)+1=n$. The second expression isn't set equal to anything, so I'm not sure what you are asking.
$endgroup$
– lulu
Jan 7 at 12:15
$begingroup$
Sorry I just corrected it - It should just be n instead of k. I originally assumed a fresh witness n = k, but I left it out here to make it more simple.
$endgroup$
– Norton
Jan 7 at 12:16
$begingroup$
I thought that when you add n+1 to 4n^2 it would be 4(n+1)^2, but that is not true I guess?
$endgroup$
– Norton
Jan 7 at 12:18
$begingroup$
The second equation is obviously false. Just take $n=0$ for example.
$endgroup$
– lulu
Jan 7 at 12:20
$begingroup$
Because $n=(n-1)+1$ and $nneq n+1$.
$endgroup$
– drhab
Jan 7 at 12:21
$begingroup$
The first equation is trivially true since $(n-1)+1=n$. The second expression isn't set equal to anything, so I'm not sure what you are asking.
$endgroup$
– lulu
Jan 7 at 12:15
$begingroup$
The first equation is trivially true since $(n-1)+1=n$. The second expression isn't set equal to anything, so I'm not sure what you are asking.
$endgroup$
– lulu
Jan 7 at 12:15
$begingroup$
Sorry I just corrected it - It should just be n instead of k. I originally assumed a fresh witness n = k, but I left it out here to make it more simple.
$endgroup$
– Norton
Jan 7 at 12:16
$begingroup$
Sorry I just corrected it - It should just be n instead of k. I originally assumed a fresh witness n = k, but I left it out here to make it more simple.
$endgroup$
– Norton
Jan 7 at 12:16
$begingroup$
I thought that when you add n+1 to 4n^2 it would be 4(n+1)^2, but that is not true I guess?
$endgroup$
– Norton
Jan 7 at 12:18
$begingroup$
I thought that when you add n+1 to 4n^2 it would be 4(n+1)^2, but that is not true I guess?
$endgroup$
– Norton
Jan 7 at 12:18
$begingroup$
The second equation is obviously false. Just take $n=0$ for example.
$endgroup$
– lulu
Jan 7 at 12:20
$begingroup$
The second equation is obviously false. Just take $n=0$ for example.
$endgroup$
– lulu
Jan 7 at 12:20
$begingroup$
Because $n=(n-1)+1$ and $nneq n+1$.
$endgroup$
– drhab
Jan 7 at 12:21
$begingroup$
Because $n=(n-1)+1$ and $nneq n+1$.
$endgroup$
– drhab
Jan 7 at 12:21
|
show 2 more comments
1 Answer
1
active
oldest
votes
0
$begingroup$
The induction step should be "Assume that $P(n-1)$ holds, and then we show that $P(n)$ holds". This is an inaccuracy in the proof. Also, you should never say "Suppose we know that $P(n)$ is true", just say "Suppose that $P(n)$ is true". (That is the induction hypothesis, not the fact that we know it...)
answered Jan 7 at 12:20
A. PongráczA. Pongrácz
5,9381929
$endgroup$
$begingroup$
I thought the inductive step in a simple induction generally was to prove k+1 holds when having assumed a fresh witness of n = k. While the inductive step in strong induction often was to prove that p(n-1) holds for p(i) where i < n. Is this a misunderstanding?
$endgroup$
– Norton
Jan 7 at 12:27
$begingroup$
There are different forms of induction. Also, it doesn't matter if you prove $P(n-1)Rightarrow P(n)$ or $P(n)Rightarrow P(n+1)$, just be consistent with your choice.
$endgroup$
– A. Pongrácz
Jan 7 at 12:29
$begingroup$
The part where this assignment doesn't make sense for me, is that they want to show that P(n) implies P(n+1) and then write "4((n-1+1)^2" instead of "4(n+1)^2".
$endgroup$
– Norton
Jan 7 at 12:31
$begingroup$
That is exactly what I put in my answer, please read it again. It is indeed an inaccuracy.
$endgroup$
– A. Pongrácz
Jan 7 at 12:34
$begingroup$
Just to clarify that I understand it correctly. We CAN choose to say that P(n) implies P(n+1) is true instead of P(n-1), but then we would have "4(n+1)^2" instead of "4((n-1)+1)^2)"?
$endgroup$
– Norton
Jan 7 at 12:39
|
show 1 more 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
});
}
});
Norton is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
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%2f3064945%2fproof-by-simple-induction-question-concerning-the-inductive-step%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
0
$begingroup$
The induction step should be "Assume that $P(n-1)$ holds, and then we show that $P(n)$ holds". This is an inaccuracy in the proof. Also, you should never say "Suppose we know that $P(n)$ is true", just say "Suppose that $P(n)$ is true". (That is the induction hypothesis, not the fact that we know it...)
answered Jan 7 at 12:20
A. PongráczA. Pongrácz
5,9381929
$endgroup$
$begingroup$
I thought the inductive step in a simple induction generally was to prove k+1 holds when having assumed a fresh witness of n = k. While the inductive step in strong induction often was to prove that p(n-1) holds for p(i) where i < n. Is this a misunderstanding?
$endgroup$
– Norton
Jan 7 at 12:27
$begingroup$
There are different forms of induction. Also, it doesn't matter if you prove $P(n-1)Rightarrow P(n)$ or $P(n)Rightarrow P(n+1)$, just be consistent with your choice.
$endgroup$
– A. Pongrácz
Jan 7 at 12:29
$begingroup$
The part where this assignment doesn't make sense for me, is that they want to show that P(n) implies P(n+1) and then write "4((n-1+1)^2" instead of "4(n+1)^2".
$endgroup$
– Norton
Jan 7 at 12:31
$begingroup$
That is exactly what I put in my answer, please read it again. It is indeed an inaccuracy.
$endgroup$
– A. Pongrácz
Jan 7 at 12:34
$begingroup$
Just to clarify that I understand it correctly. We CAN choose to say that P(n) implies P(n+1) is true instead of P(n-1), but then we would have "4(n+1)^2" instead of "4((n-1)+1)^2)"?
$endgroup$
– Norton
Jan 7 at 12:39
|
show 1 more comment
0
$begingroup$
The induction step should be "Assume that $P(n-1)$ holds, and then we show that $P(n)$ holds". This is an inaccuracy in the proof. Also, you should never say "Suppose we know that $P(n)$ is true", just say "Suppose that $P(n)$ is true". (That is the induction hypothesis, not the fact that we know it...)
answered Jan 7 at 12:20
A. PongráczA. Pongrácz
5,9381929
$endgroup$
$begingroup$
I thought the inductive step in a simple induction generally was to prove k+1 holds when having assumed a fresh witness of n = k. While the inductive step in strong induction often was to prove that p(n-1) holds for p(i) where i < n. Is this a misunderstanding?
$endgroup$
– Norton
Jan 7 at 12:27
$begingroup$
There are different forms of induction. Also, it doesn't matter if you prove $P(n-1)Rightarrow P(n)$ or $P(n)Rightarrow P(n+1)$, just be consistent with your choice.
$endgroup$
– A. Pongrácz
Jan 7 at 12:29
$begingroup$
The part where this assignment doesn't make sense for me, is that they want to show that P(n) implies P(n+1) and then write "4((n-1+1)^2" instead of "4(n+1)^2".
$endgroup$
– Norton
Jan 7 at 12:31
$begingroup$
That is exactly what I put in my answer, please read it again. It is indeed an inaccuracy.
$endgroup$
– A. Pongrácz
Jan 7 at 12:34
$begingroup$
Just to clarify that I understand it correctly. We CAN choose to say that P(n) implies P(n+1) is true instead of P(n-1), but then we would have "4(n+1)^2" instead of "4((n-1)+1)^2)"?
$endgroup$
– Norton
Jan 7 at 12:39
|
show 1 more comment
0
0
0
$begingroup$
The induction step should be "Assume that $P(n-1)$ holds, and then we show that $P(n)$ holds". This is an inaccuracy in the proof. Also, you should never say "Suppose we know that $P(n)$ is true", just say "Suppose that $P(n)$ is true". (That is the induction hypothesis, not the fact that we know it...)
answered Jan 7 at 12:20
A. PongráczA. Pongrácz
5,9381929
$endgroup$
The induction step should be "Assume that $P(n-1)$ holds, and then we show that $P(n)$ holds". This is an inaccuracy in the proof. Also, you should never say "Suppose we know that $P(n)$ is true", just say "Suppose that $P(n)$ is true". (That is the induction hypothesis, not the fact that we know it...)
answered Jan 7 at 12:20
A. PongráczA. Pongrácz
5,9381929
answered Jan 7 at 12:20
A. PongráczA. Pongrácz
5,9381929
answered Jan 7 at 12:20
A. PongráczA. Pongrácz
5,9381929
answered Jan 7 at 12:20
A. PongráczA. Pongrácz
5,9381929
5,9381929
$begingroup$
I thought the inductive step in a simple induction generally was to prove k+1 holds when having assumed a fresh witness of n = k. While the inductive step in strong induction often was to prove that p(n-1) holds for p(i) where i < n. Is this a misunderstanding?
$endgroup$
– Norton
Jan 7 at 12:27
$begingroup$
There are different forms of induction. Also, it doesn't matter if you prove $P(n-1)Rightarrow P(n)$ or $P(n)Rightarrow P(n+1)$, just be consistent with your choice.
$endgroup$
– A. Pongrácz
Jan 7 at 12:29
$begingroup$
The part where this assignment doesn't make sense for me, is that they want to show that P(n) implies P(n+1) and then write "4((n-1+1)^2" instead of "4(n+1)^2".
$endgroup$
– Norton
Jan 7 at 12:31
$begingroup$
That is exactly what I put in my answer, please read it again. It is indeed an inaccuracy.
$endgroup$
– A. Pongrácz
Jan 7 at 12:34
$begingroup$
Just to clarify that I understand it correctly. We CAN choose to say that P(n) implies P(n+1) is true instead of P(n-1), but then we would have "4(n+1)^2" instead of "4((n-1)+1)^2)"?
$endgroup$
– Norton
Jan 7 at 12:39
|
show 1 more comment
$begingroup$
I thought the inductive step in a simple induction generally was to prove k+1 holds when having assumed a fresh witness of n = k. While the inductive step in strong induction often was to prove that p(n-1) holds for p(i) where i < n. Is this a misunderstanding?
$endgroup$
– Norton
Jan 7 at 12:27
$begingroup$
There are different forms of induction. Also, it doesn't matter if you prove $P(n-1)Rightarrow P(n)$ or $P(n)Rightarrow P(n+1)$, just be consistent with your choice.
$endgroup$
– A. Pongrácz
Jan 7 at 12:29
$begingroup$
The part where this assignment doesn't make sense for me, is that they want to show that P(n) implies P(n+1) and then write "4((n-1+1)^2" instead of "4(n+1)^2".
$endgroup$
– Norton
Jan 7 at 12:31
$begingroup$
That is exactly what I put in my answer, please read it again. It is indeed an inaccuracy.
$endgroup$
– A. Pongrácz
Jan 7 at 12:34
$begingroup$
Just to clarify that I understand it correctly. We CAN choose to say that P(n) implies P(n+1) is true instead of P(n-1), but then we would have "4(n+1)^2" instead of "4((n-1)+1)^2)"?
$endgroup$
– Norton
Jan 7 at 12:39
$begingroup$
I thought the inductive step in a simple induction generally was to prove k+1 holds when having assumed a fresh witness of n = k. While the inductive step in strong induction often was to prove that p(n-1) holds for p(i) where i < n. Is this a misunderstanding?
$endgroup$
– Norton
Jan 7 at 12:27
$begingroup$
I thought the inductive step in a simple induction generally was to prove k+1 holds when having assumed a fresh witness of n = k. While the inductive step in strong induction often was to prove that p(n-1) holds for p(i) where i < n. Is this a misunderstanding?
$endgroup$
– Norton
Jan 7 at 12:27
$begingroup$
There are different forms of induction. Also, it doesn't matter if you prove $P(n-1)Rightarrow P(n)$ or $P(n)Rightarrow P(n+1)$, just be consistent with your choice.
$endgroup$
– A. Pongrácz
Jan 7 at 12:29
$begingroup$
There are different forms of induction. Also, it doesn't matter if you prove $P(n-1)Rightarrow P(n)$ or $P(n)Rightarrow P(n+1)$, just be consistent with your choice.
$endgroup$
– A. Pongrácz
Jan 7 at 12:29
$begingroup$
The part where this assignment doesn't make sense for me, is that they want to show that P(n) implies P(n+1) and then write "4((n-1+1)^2" instead of "4(n+1)^2".
$endgroup$
– Norton
Jan 7 at 12:31
$begingroup$
The part where this assignment doesn't make sense for me, is that they want to show that P(n) implies P(n+1) and then write "4((n-1+1)^2" instead of "4(n+1)^2".
$endgroup$
– Norton
Jan 7 at 12:31
$begingroup$
That is exactly what I put in my answer, please read it again. It is indeed an inaccuracy.
$endgroup$
– A. Pongrácz
Jan 7 at 12:34
$begingroup$
That is exactly what I put in my answer, please read it again. It is indeed an inaccuracy.
$endgroup$
– A. Pongrácz
Jan 7 at 12:34
$begingroup$
Just to clarify that I understand it correctly. We CAN choose to say that P(n) implies P(n+1) is true instead of P(n-1), but then we would have "4(n+1)^2" instead of "4((n-1)+1)^2)"?
$endgroup$
– Norton
Jan 7 at 12:39
$begingroup$
Just to clarify that I understand it correctly. We CAN choose to say that P(n) implies P(n+1) is true instead of P(n-1), but then we would have "4(n+1)^2" instead of "4((n-1)+1)^2)"?
$endgroup$
– Norton
Jan 7 at 12:39
|
show 1 more comment
Norton is a new contributor. Be nice, and check out our Code of Conduct.
draft saved
draft discarded
Norton is a new contributor. Be nice, and check out our Code of Conduct.
Norton is a new contributor. Be nice, and check out our Code of Conduct.
Norton is a new contributor. Be nice, and check out our Code of Conduct.
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.
draft saved
draft discarded
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%2f3064945%2fproof-by-simple-induction-question-concerning-the-inductive-step%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$
The first equation is trivially true since $(n-1)+1=n$. The second expression isn't set equal to anything, so I'm not sure what you are asking.
$endgroup$
– lulu
Jan 7 at 12:15
$begingroup$
Sorry I just corrected it - It should just be n instead of k. I originally assumed a fresh witness n = k, but I left it out here to make it more simple.
$endgroup$
– Norton
Jan 7 at 12:16
$begingroup$
I thought that when you add n+1 to 4n^2 it would be 4(n+1)^2, but that is not true I guess?
$endgroup$
– Norton
Jan 7 at 12:18
$begingroup$
The second equation is obviously false. Just take $n=0$ for example.
$endgroup$
– lulu
Jan 7 at 12:20
$begingroup$
Because $n=(n-1)+1$ and $nneq n+1$.
$endgroup$
– drhab
Jan 7 at 12:21