Proof by induction that $frac13(n^3-n)$ is an integer. Am I on the correct path?
2
$begingroup$
I have been trying to prove $$frac{n^3-n}{3}=kin mathbb N $$
I have tried the following calculations, have however difficulties in the final step.
Could you help me out?
Here are my calculations:
proof-verification induction
edited Dec 16 '18 at 18:50
J.G.
29.4k22846
asked Dec 16 '18 at 18:40
thebillythebilly
566
$endgroup$
add a comment |
2
$begingroup$
I have been trying to prove $$frac{n^3-n}{3}=kin mathbb N $$
I have tried the following calculations, have however difficulties in the final step.
Could you help me out?
Here are my calculations:
proof-verification induction
edited Dec 16 '18 at 18:50
J.G.
29.4k22846
asked Dec 16 '18 at 18:40
thebillythebilly
566
$endgroup$
$begingroup$
Yeah I know, I forgot the induction hypothesis, but I just left it out, as those are just some exercises for myself, nothing I need to hand in...
$endgroup$
– thebilly
Dec 16 '18 at 18:41
$begingroup$
Since $n^2$ and $n$ are naturals, and naturals are closed under addition, we have the conclusion right?
$endgroup$
– Andrew Li
Dec 16 '18 at 18:45
add a comment |
2
2
2
$begingroup$
I have been trying to prove $$frac{n^3-n}{3}=kin mathbb N $$
I have tried the following calculations, have however difficulties in the final step.
Could you help me out?
Here are my calculations:
proof-verification induction
edited Dec 16 '18 at 18:50
J.G.
29.4k22846
asked Dec 16 '18 at 18:40
thebillythebilly
566
$endgroup$
I have been trying to prove $$frac{n^3-n}{3}=kin mathbb N $$
I have tried the following calculations, have however difficulties in the final step.
Could you help me out?
Here are my calculations:
proof-verification induction
proof-verification induction
edited Dec 16 '18 at 18:50
J.G.
29.4k22846
asked Dec 16 '18 at 18:40
thebillythebilly
566
edited Dec 16 '18 at 18:50
J.G.
29.4k22846
asked Dec 16 '18 at 18:40
thebillythebilly
566
edited Dec 16 '18 at 18:50
J.G.
29.4k22846
edited Dec 16 '18 at 18:50
J.G.
29.4k22846
edited Dec 16 '18 at 18:50
J.G.
29.4k22846
29.4k22846
asked Dec 16 '18 at 18:40
thebillythebilly
566
asked Dec 16 '18 at 18:40
thebillythebilly
566
asked Dec 16 '18 at 18:40
thebillythebilly
566
566
$begingroup$
Yeah I know, I forgot the induction hypothesis, but I just left it out, as those are just some exercises for myself, nothing I need to hand in...
$endgroup$
– thebilly
Dec 16 '18 at 18:41
$begingroup$
Since $n^2$ and $n$ are naturals, and naturals are closed under addition, we have the conclusion right?
$endgroup$
– Andrew Li
Dec 16 '18 at 18:45
add a comment |
$begingroup$
Yeah I know, I forgot the induction hypothesis, but I just left it out, as those are just some exercises for myself, nothing I need to hand in...
$endgroup$
– thebilly
Dec 16 '18 at 18:41
$begingroup$
Since $n^2$ and $n$ are naturals, and naturals are closed under addition, we have the conclusion right?
$endgroup$
– Andrew Li
Dec 16 '18 at 18:45
$begingroup$
Yeah I know, I forgot the induction hypothesis, but I just left it out, as those are just some exercises for myself, nothing I need to hand in...
$endgroup$
– thebilly
Dec 16 '18 at 18:41
$begingroup$
Yeah I know, I forgot the induction hypothesis, but I just left it out, as those are just some exercises for myself, nothing I need to hand in...
$endgroup$
– thebilly
Dec 16 '18 at 18:41
$begingroup$
Since $n^2$ and $n$ are naturals, and naturals are closed under addition, we have the conclusion right?
$endgroup$
– Andrew Li
Dec 16 '18 at 18:45
$begingroup$
Since $n^2$ and $n$ are naturals, and naturals are closed under addition, we have the conclusion right?
$endgroup$
– Andrew Li
Dec 16 '18 at 18:45
add a comment |
5 Answers
5
active
oldest
votes
4
$begingroup$
I suspect the $k$ in $k in mathbb N$ is confusing you
You have shown that $dfrac{(n+1)^3-(n+1)}{3}=dfrac{n^3-n}{3} +n^2+n$ and you know that
$dfrac{n^3-n}{3}$ is an element of $mathbb N$ (by hypothesis)
$n^2+n$ is an element of $mathbb N$ (multiplication and addition of integers)
$dfrac{n^3-n}{3} +n^2+n$ is an element of $mathbb N$ (addition of integers)
so $dfrac{(n+1)^3-(n+1)}{3}$ is an element of $mathbb N$, quod erat demonstrandum
answered Dec 16 '18 at 18:51
HenryHenry
101k481168
$endgroup$
$begingroup$
Thank you. But do I not need to transform everything in a way such that the original statement is visible again? ( I do not know how, but in another formula I transformed it such that I had the original statement, with all n's changed to n+1....)
$endgroup$
– thebilly
Dec 16 '18 at 19:51
$begingroup$
@thebilly You want to show $frac{n^3-n}{3}in mathbb N$ by induction. You proved it for $n=2$. I would say that the next step should be something like "if it is true for $n=m$ then it is true for $n=m+1$ because $frac{(m+1)^3-(m+1)}{3}=frac{m^3-m}{3} +m^2+m$ which is a positive integer". Finally you say the hypothesis is true for all integer $nge 2$ by induction. And you are done
$endgroup$
– Henry
Dec 16 '18 at 21:15
$begingroup$
Thank you for your help.
$endgroup$
– thebilly
Dec 17 '18 at 7:10
add a comment |
3
$begingroup$
Hint: Note that
$$frac{n^3-n}{3} = frac{n(n^2-1)}{3} = frac{n(n+1)(n-1)}{3}$$
From here, you have a product of three consecutive integers in the numerator. What can you conclude from that?
answered Dec 16 '18 at 18:54
KM101KM101
6,0801525
$endgroup$
$begingroup$
that the product of those integers is an integer as well?
$endgroup$
– thebilly
Dec 16 '18 at 19:47
1
$begingroup$
Any three consecutive integers must include a multiple of $3$, so their product must also be a multiple of $3$. (At the time I typed this, I didn’t see the induction part, so you can just keep this in mind as an alternative approach perhaps.)
$endgroup$
– KM101
Dec 16 '18 at 19:48
$begingroup$
I see. Thank you.
$endgroup$
– thebilly
Dec 17 '18 at 7:11
add a comment |
2
$begingroup$
$frac {n^3-n}3+n^2+n=frac {n^3+3n^2+3n-n}3=frac {n^3+3n^2+3n+1-n-1}3=frac {(n+1)^3-(n+1)}3$
answered Dec 16 '18 at 18:45
Mohammad Zuhair KhanMohammad Zuhair Khan
1,6682625
$endgroup$
add a comment |
1
$begingroup$
Hypothesis : $3|(n^3-n)$.
Step $n+1$:
$(n+1)^3 -(n+1)=$
$(n^3 +3n^3+3n+1) -n -1=$
$(n^3-n)+ 3(n^3+n)$ ;
The second term is divisible by 3, so is the first term by hypothesis.
answered Dec 16 '18 at 20:19
Peter SzilasPeter Szilas
11.5k2822
$endgroup$
$begingroup$
Ah right. Thank you.
$endgroup$
– thebilly
Dec 17 '18 at 7:12
$begingroup$
thebilly.Welcome:)
$endgroup$
– Peter Szilas
Dec 17 '18 at 8:32
add a comment |
0
$begingroup$
For the induction, you, in fact, reach your goal since $frac{n^3-n}{3}$ is an integer by the inductive hypothesis.
If you do not to prove it with induction, there are other ways to do so.
- Consider Fermat Little Theorem. This theorem says that $n^p-n$ is always divisible by $p$ where $p$ is a prime. You just reach your goal in one step!
- You may also notice that $n^3-n = n(n^2-1) = (n-1)n(n+1)$. Now, one of these three consecutive integers must be divisible by $3$. This also follows from a theorem saying that, any $k$ consecutive integers is divisible by $k!$. According to this theorem, this number is divisible by $6$ too!
answered Dec 16 '18 at 21:41
Maged SaeedMaged Saeed
8821417
$endgroup$
1
$begingroup$
Thank you. I'll remember the second bullet point. This comes up a lot in my exercises...
$endgroup$
– thebilly
Dec 17 '18 at 7:10
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
});
}
});
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%2f3042977%2fproof-by-induction-that-frac13n3-n-is-an-integer-am-i-on-the-correct-path%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
4
$begingroup$
I suspect the $k$ in $k in mathbb N$ is confusing you
You have shown that $dfrac{(n+1)^3-(n+1)}{3}=dfrac{n^3-n}{3} +n^2+n$ and you know that
$dfrac{n^3-n}{3}$ is an element of $mathbb N$ (by hypothesis)
$n^2+n$ is an element of $mathbb N$ (multiplication and addition of integers)
$dfrac{n^3-n}{3} +n^2+n$ is an element of $mathbb N$ (addition of integers)
so $dfrac{(n+1)^3-(n+1)}{3}$ is an element of $mathbb N$, quod erat demonstrandum
answered Dec 16 '18 at 18:51
HenryHenry
101k481168
$endgroup$
$begingroup$
Thank you. But do I not need to transform everything in a way such that the original statement is visible again? ( I do not know how, but in another formula I transformed it such that I had the original statement, with all n's changed to n+1....)
$endgroup$
– thebilly
Dec 16 '18 at 19:51
$begingroup$
@thebilly You want to show $frac{n^3-n}{3}in mathbb N$ by induction. You proved it for $n=2$. I would say that the next step should be something like "if it is true for $n=m$ then it is true for $n=m+1$ because $frac{(m+1)^3-(m+1)}{3}=frac{m^3-m}{3} +m^2+m$ which is a positive integer". Finally you say the hypothesis is true for all integer $nge 2$ by induction. And you are done
$endgroup$
– Henry
Dec 16 '18 at 21:15
$begingroup$
Thank you for your help.
$endgroup$
– thebilly
Dec 17 '18 at 7:10
add a comment |
4
$begingroup$
I suspect the $k$ in $k in mathbb N$ is confusing you
You have shown that $dfrac{(n+1)^3-(n+1)}{3}=dfrac{n^3-n}{3} +n^2+n$ and you know that
$dfrac{n^3-n}{3}$ is an element of $mathbb N$ (by hypothesis)
$n^2+n$ is an element of $mathbb N$ (multiplication and addition of integers)
$dfrac{n^3-n}{3} +n^2+n$ is an element of $mathbb N$ (addition of integers)
so $dfrac{(n+1)^3-(n+1)}{3}$ is an element of $mathbb N$, quod erat demonstrandum
answered Dec 16 '18 at 18:51
HenryHenry
101k481168
$endgroup$
$begingroup$
Thank you. But do I not need to transform everything in a way such that the original statement is visible again? ( I do not know how, but in another formula I transformed it such that I had the original statement, with all n's changed to n+1....)
$endgroup$
– thebilly
Dec 16 '18 at 19:51
$begingroup$
@thebilly You want to show $frac{n^3-n}{3}in mathbb N$ by induction. You proved it for $n=2$. I would say that the next step should be something like "if it is true for $n=m$ then it is true for $n=m+1$ because $frac{(m+1)^3-(m+1)}{3}=frac{m^3-m}{3} +m^2+m$ which is a positive integer". Finally you say the hypothesis is true for all integer $nge 2$ by induction. And you are done
$endgroup$
– Henry
Dec 16 '18 at 21:15
$begingroup$
Thank you for your help.
$endgroup$
– thebilly
Dec 17 '18 at 7:10
add a comment |
4
4
4
$begingroup$
I suspect the $k$ in $k in mathbb N$ is confusing you
You have shown that $dfrac{(n+1)^3-(n+1)}{3}=dfrac{n^3-n}{3} +n^2+n$ and you know that
$dfrac{n^3-n}{3}$ is an element of $mathbb N$ (by hypothesis)
$n^2+n$ is an element of $mathbb N$ (multiplication and addition of integers)
$dfrac{n^3-n}{3} +n^2+n$ is an element of $mathbb N$ (addition of integers)
so $dfrac{(n+1)^3-(n+1)}{3}$ is an element of $mathbb N$, quod erat demonstrandum
answered Dec 16 '18 at 18:51
HenryHenry
101k481168
$endgroup$
I suspect the $k$ in $k in mathbb N$ is confusing you
You have shown that $dfrac{(n+1)^3-(n+1)}{3}=dfrac{n^3-n}{3} +n^2+n$ and you know that
$dfrac{n^3-n}{3}$ is an element of $mathbb N$ (by hypothesis)
$n^2+n$ is an element of $mathbb N$ (multiplication and addition of integers)
$dfrac{n^3-n}{3} +n^2+n$ is an element of $mathbb N$ (addition of integers)
so $dfrac{(n+1)^3-(n+1)}{3}$ is an element of $mathbb N$, quod erat demonstrandum
answered Dec 16 '18 at 18:51
HenryHenry
101k481168
answered Dec 16 '18 at 18:51
HenryHenry
101k481168
answered Dec 16 '18 at 18:51
HenryHenry
101k481168
answered Dec 16 '18 at 18:51
HenryHenry
101k481168
101k481168
$begingroup$
Thank you. But do I not need to transform everything in a way such that the original statement is visible again? ( I do not know how, but in another formula I transformed it such that I had the original statement, with all n's changed to n+1....)
$endgroup$
– thebilly
Dec 16 '18 at 19:51
$begingroup$
@thebilly You want to show $frac{n^3-n}{3}in mathbb N$ by induction. You proved it for $n=2$. I would say that the next step should be something like "if it is true for $n=m$ then it is true for $n=m+1$ because $frac{(m+1)^3-(m+1)}{3}=frac{m^3-m}{3} +m^2+m$ which is a positive integer". Finally you say the hypothesis is true for all integer $nge 2$ by induction. And you are done
$endgroup$
– Henry
Dec 16 '18 at 21:15
$begingroup$
Thank you for your help.
$endgroup$
– thebilly
Dec 17 '18 at 7:10
add a comment |
$begingroup$
Thank you. But do I not need to transform everything in a way such that the original statement is visible again? ( I do not know how, but in another formula I transformed it such that I had the original statement, with all n's changed to n+1....)
$endgroup$
– thebilly
Dec 16 '18 at 19:51
$begingroup$
@thebilly You want to show $frac{n^3-n}{3}in mathbb N$ by induction. You proved it for $n=2$. I would say that the next step should be something like "if it is true for $n=m$ then it is true for $n=m+1$ because $frac{(m+1)^3-(m+1)}{3}=frac{m^3-m}{3} +m^2+m$ which is a positive integer". Finally you say the hypothesis is true for all integer $nge 2$ by induction. And you are done
$endgroup$
– Henry
Dec 16 '18 at 21:15
$begingroup$
Thank you for your help.
$endgroup$
– thebilly
Dec 17 '18 at 7:10
$begingroup$
Thank you. But do I not need to transform everything in a way such that the original statement is visible again? ( I do not know how, but in another formula I transformed it such that I had the original statement, with all n's changed to n+1....)
$endgroup$
– thebilly
Dec 16 '18 at 19:51
$begingroup$
Thank you. But do I not need to transform everything in a way such that the original statement is visible again? ( I do not know how, but in another formula I transformed it such that I had the original statement, with all n's changed to n+1....)
$endgroup$
– thebilly
Dec 16 '18 at 19:51
$begingroup$
@thebilly You want to show $frac{n^3-n}{3}in mathbb N$ by induction. You proved it for $n=2$. I would say that the next step should be something like "if it is true for $n=m$ then it is true for $n=m+1$ because $frac{(m+1)^3-(m+1)}{3}=frac{m^3-m}{3} +m^2+m$ which is a positive integer". Finally you say the hypothesis is true for all integer $nge 2$ by induction. And you are done
$endgroup$
– Henry
Dec 16 '18 at 21:15
$begingroup$
@thebilly You want to show $frac{n^3-n}{3}in mathbb N$ by induction. You proved it for $n=2$. I would say that the next step should be something like "if it is true for $n=m$ then it is true for $n=m+1$ because $frac{(m+1)^3-(m+1)}{3}=frac{m^3-m}{3} +m^2+m$ which is a positive integer". Finally you say the hypothesis is true for all integer $nge 2$ by induction. And you are done
$endgroup$
– Henry
Dec 16 '18 at 21:15
$begingroup$
Thank you for your help.
$endgroup$
– thebilly
Dec 17 '18 at 7:10
$begingroup$
Thank you for your help.
$endgroup$
– thebilly
Dec 17 '18 at 7:10
add a comment |
3
$begingroup$
Hint: Note that
$$frac{n^3-n}{3} = frac{n(n^2-1)}{3} = frac{n(n+1)(n-1)}{3}$$
From here, you have a product of three consecutive integers in the numerator. What can you conclude from that?
answered Dec 16 '18 at 18:54
KM101KM101
6,0801525
$endgroup$
$begingroup$
that the product of those integers is an integer as well?
$endgroup$
– thebilly
Dec 16 '18 at 19:47
1
$begingroup$
Any three consecutive integers must include a multiple of $3$, so their product must also be a multiple of $3$. (At the time I typed this, I didn’t see the induction part, so you can just keep this in mind as an alternative approach perhaps.)
$endgroup$
– KM101
Dec 16 '18 at 19:48
$begingroup$
I see. Thank you.
$endgroup$
– thebilly
Dec 17 '18 at 7:11
add a comment |
3
$begingroup$
Hint: Note that
$$frac{n^3-n}{3} = frac{n(n^2-1)}{3} = frac{n(n+1)(n-1)}{3}$$
From here, you have a product of three consecutive integers in the numerator. What can you conclude from that?
answered Dec 16 '18 at 18:54
KM101KM101
6,0801525
$endgroup$
$begingroup$
that the product of those integers is an integer as well?
$endgroup$
– thebilly
Dec 16 '18 at 19:47
1
$begingroup$
Any three consecutive integers must include a multiple of $3$, so their product must also be a multiple of $3$. (At the time I typed this, I didn’t see the induction part, so you can just keep this in mind as an alternative approach perhaps.)
$endgroup$
– KM101
Dec 16 '18 at 19:48
$begingroup$
I see. Thank you.
$endgroup$
– thebilly
Dec 17 '18 at 7:11
add a comment |
3
3
3
$begingroup$
Hint: Note that
$$frac{n^3-n}{3} = frac{n(n^2-1)}{3} = frac{n(n+1)(n-1)}{3}$$
From here, you have a product of three consecutive integers in the numerator. What can you conclude from that?
answered Dec 16 '18 at 18:54
KM101KM101
6,0801525
$endgroup$
Hint: Note that
$$frac{n^3-n}{3} = frac{n(n^2-1)}{3} = frac{n(n+1)(n-1)}{3}$$
From here, you have a product of three consecutive integers in the numerator. What can you conclude from that?
answered Dec 16 '18 at 18:54
KM101KM101
6,0801525
answered Dec 16 '18 at 18:54
KM101KM101
6,0801525
answered Dec 16 '18 at 18:54
KM101KM101
6,0801525
answered Dec 16 '18 at 18:54
KM101KM101
6,0801525
6,0801525
$begingroup$
that the product of those integers is an integer as well?
$endgroup$
– thebilly
Dec 16 '18 at 19:47
1
$begingroup$
Any three consecutive integers must include a multiple of $3$, so their product must also be a multiple of $3$. (At the time I typed this, I didn’t see the induction part, so you can just keep this in mind as an alternative approach perhaps.)
$endgroup$
– KM101
Dec 16 '18 at 19:48
$begingroup$
I see. Thank you.
$endgroup$
– thebilly
Dec 17 '18 at 7:11
add a comment |
$begingroup$
that the product of those integers is an integer as well?
$endgroup$
– thebilly
Dec 16 '18 at 19:47
1
$begingroup$
Any three consecutive integers must include a multiple of $3$, so their product must also be a multiple of $3$. (At the time I typed this, I didn’t see the induction part, so you can just keep this in mind as an alternative approach perhaps.)
$endgroup$
– KM101
Dec 16 '18 at 19:48
$begingroup$
I see. Thank you.
$endgroup$
– thebilly
Dec 17 '18 at 7:11
$begingroup$
that the product of those integers is an integer as well?
$endgroup$
– thebilly
Dec 16 '18 at 19:47
$begingroup$
that the product of those integers is an integer as well?
$endgroup$
– thebilly
Dec 16 '18 at 19:47
1
1
$begingroup$
Any three consecutive integers must include a multiple of $3$, so their product must also be a multiple of $3$. (At the time I typed this, I didn’t see the induction part, so you can just keep this in mind as an alternative approach perhaps.)
$endgroup$
– KM101
Dec 16 '18 at 19:48
$begingroup$
Any three consecutive integers must include a multiple of $3$, so their product must also be a multiple of $3$. (At the time I typed this, I didn’t see the induction part, so you can just keep this in mind as an alternative approach perhaps.)
$endgroup$
– KM101
Dec 16 '18 at 19:48
$begingroup$
I see. Thank you.
$endgroup$
– thebilly
Dec 17 '18 at 7:11
$begingroup$
I see. Thank you.
$endgroup$
– thebilly
Dec 17 '18 at 7:11
add a comment |
2
$begingroup$
$frac {n^3-n}3+n^2+n=frac {n^3+3n^2+3n-n}3=frac {n^3+3n^2+3n+1-n-1}3=frac {(n+1)^3-(n+1)}3$
answered Dec 16 '18 at 18:45
Mohammad Zuhair KhanMohammad Zuhair Khan
1,6682625
$endgroup$
add a comment |
2
$begingroup$
$frac {n^3-n}3+n^2+n=frac {n^3+3n^2+3n-n}3=frac {n^3+3n^2+3n+1-n-1}3=frac {(n+1)^3-(n+1)}3$
answered Dec 16 '18 at 18:45
Mohammad Zuhair KhanMohammad Zuhair Khan
1,6682625
$endgroup$
add a comment |
2
2
2
$begingroup$
$frac {n^3-n}3+n^2+n=frac {n^3+3n^2+3n-n}3=frac {n^3+3n^2+3n+1-n-1}3=frac {(n+1)^3-(n+1)}3$
answered Dec 16 '18 at 18:45
Mohammad Zuhair KhanMohammad Zuhair Khan
1,6682625
$endgroup$
$frac {n^3-n}3+n^2+n=frac {n^3+3n^2+3n-n}3=frac {n^3+3n^2+3n+1-n-1}3=frac {(n+1)^3-(n+1)}3$
answered Dec 16 '18 at 18:45
Mohammad Zuhair KhanMohammad Zuhair Khan
1,6682625
answered Dec 16 '18 at 18:45
Mohammad Zuhair KhanMohammad Zuhair Khan
1,6682625
answered Dec 16 '18 at 18:45
Mohammad Zuhair KhanMohammad Zuhair Khan
1,6682625
answered Dec 16 '18 at 18:45
Mohammad Zuhair KhanMohammad Zuhair Khan
1,6682625
1,6682625
add a comment |
add a comment |
1
$begingroup$
Hypothesis : $3|(n^3-n)$.
Step $n+1$:
$(n+1)^3 -(n+1)=$
$(n^3 +3n^3+3n+1) -n -1=$
$(n^3-n)+ 3(n^3+n)$ ;
The second term is divisible by 3, so is the first term by hypothesis.
answered Dec 16 '18 at 20:19
Peter SzilasPeter Szilas
11.5k2822
$endgroup$
$begingroup$
Ah right. Thank you.
$endgroup$
– thebilly
Dec 17 '18 at 7:12
$begingroup$
thebilly.Welcome:)
$endgroup$
– Peter Szilas
Dec 17 '18 at 8:32
add a comment |
1
$begingroup$
Hypothesis : $3|(n^3-n)$.
Step $n+1$:
$(n+1)^3 -(n+1)=$
$(n^3 +3n^3+3n+1) -n -1=$
$(n^3-n)+ 3(n^3+n)$ ;
The second term is divisible by 3, so is the first term by hypothesis.
answered Dec 16 '18 at 20:19
Peter SzilasPeter Szilas
11.5k2822
$endgroup$
$begingroup$
Ah right. Thank you.
$endgroup$
– thebilly
Dec 17 '18 at 7:12
$begingroup$
thebilly.Welcome:)
$endgroup$
– Peter Szilas
Dec 17 '18 at 8:32
add a comment |
1
1
1
$begingroup$
Hypothesis : $3|(n^3-n)$.
Step $n+1$:
$(n+1)^3 -(n+1)=$
$(n^3 +3n^3+3n+1) -n -1=$
$(n^3-n)+ 3(n^3+n)$ ;
The second term is divisible by 3, so is the first term by hypothesis.
answered Dec 16 '18 at 20:19
Peter SzilasPeter Szilas
11.5k2822
$endgroup$
Hypothesis : $3|(n^3-n)$.
Step $n+1$:
$(n+1)^3 -(n+1)=$
$(n^3 +3n^3+3n+1) -n -1=$
$(n^3-n)+ 3(n^3+n)$ ;
The second term is divisible by 3, so is the first term by hypothesis.
answered Dec 16 '18 at 20:19
Peter SzilasPeter Szilas
11.5k2822
answered Dec 16 '18 at 20:19
Peter SzilasPeter Szilas
11.5k2822
answered Dec 16 '18 at 20:19
Peter SzilasPeter Szilas
11.5k2822
answered Dec 16 '18 at 20:19
Peter SzilasPeter Szilas
11.5k2822
11.5k2822
$begingroup$
Ah right. Thank you.
$endgroup$
– thebilly
Dec 17 '18 at 7:12
$begingroup$
thebilly.Welcome:)
$endgroup$
– Peter Szilas
Dec 17 '18 at 8:32
add a comment |
$begingroup$
Ah right. Thank you.
$endgroup$
– thebilly
Dec 17 '18 at 7:12
$begingroup$
thebilly.Welcome:)
$endgroup$
– Peter Szilas
Dec 17 '18 at 8:32
$begingroup$
Ah right. Thank you.
$endgroup$
– thebilly
Dec 17 '18 at 7:12
$begingroup$
Ah right. Thank you.
$endgroup$
– thebilly
Dec 17 '18 at 7:12
$begingroup$
thebilly.Welcome:)
$endgroup$
– Peter Szilas
Dec 17 '18 at 8:32
$begingroup$
thebilly.Welcome:)
$endgroup$
– Peter Szilas
Dec 17 '18 at 8:32
add a comment |
0
$begingroup$
For the induction, you, in fact, reach your goal since $frac{n^3-n}{3}$ is an integer by the inductive hypothesis.
If you do not to prove it with induction, there are other ways to do so.
- Consider Fermat Little Theorem. This theorem says that $n^p-n$ is always divisible by $p$ where $p$ is a prime. You just reach your goal in one step!
- You may also notice that $n^3-n = n(n^2-1) = (n-1)n(n+1)$. Now, one of these three consecutive integers must be divisible by $3$. This also follows from a theorem saying that, any $k$ consecutive integers is divisible by $k!$. According to this theorem, this number is divisible by $6$ too!
answered Dec 16 '18 at 21:41
Maged SaeedMaged Saeed
8821417
$endgroup$
1
$begingroup$
Thank you. I'll remember the second bullet point. This comes up a lot in my exercises...
$endgroup$
– thebilly
Dec 17 '18 at 7:10
add a comment |
0
$begingroup$
For the induction, you, in fact, reach your goal since $frac{n^3-n}{3}$ is an integer by the inductive hypothesis.
If you do not to prove it with induction, there are other ways to do so.
- Consider Fermat Little Theorem. This theorem says that $n^p-n$ is always divisible by $p$ where $p$ is a prime. You just reach your goal in one step!
- You may also notice that $n^3-n = n(n^2-1) = (n-1)n(n+1)$. Now, one of these three consecutive integers must be divisible by $3$. This also follows from a theorem saying that, any $k$ consecutive integers is divisible by $k!$. According to this theorem, this number is divisible by $6$ too!
answered Dec 16 '18 at 21:41
Maged SaeedMaged Saeed
8821417
$endgroup$
1
$begingroup$
Thank you. I'll remember the second bullet point. This comes up a lot in my exercises...
$endgroup$
– thebilly
Dec 17 '18 at 7:10
add a comment |
0
0
0
$begingroup$
For the induction, you, in fact, reach your goal since $frac{n^3-n}{3}$ is an integer by the inductive hypothesis.
If you do not to prove it with induction, there are other ways to do so.
- Consider Fermat Little Theorem. This theorem says that $n^p-n$ is always divisible by $p$ where $p$ is a prime. You just reach your goal in one step!
- You may also notice that $n^3-n = n(n^2-1) = (n-1)n(n+1)$. Now, one of these three consecutive integers must be divisible by $3$. This also follows from a theorem saying that, any $k$ consecutive integers is divisible by $k!$. According to this theorem, this number is divisible by $6$ too!
answered Dec 16 '18 at 21:41
Maged SaeedMaged Saeed
8821417
$endgroup$
For the induction, you, in fact, reach your goal since $frac{n^3-n}{3}$ is an integer by the inductive hypothesis.
If you do not to prove it with induction, there are other ways to do so.
- Consider Fermat Little Theorem. This theorem says that $n^p-n$ is always divisible by $p$ where $p$ is a prime. You just reach your goal in one step!
- You may also notice that $n^3-n = n(n^2-1) = (n-1)n(n+1)$. Now, one of these three consecutive integers must be divisible by $3$. This also follows from a theorem saying that, any $k$ consecutive integers is divisible by $k!$. According to this theorem, this number is divisible by $6$ too!
answered Dec 16 '18 at 21:41
Maged SaeedMaged Saeed
8821417
answered Dec 16 '18 at 21:41
Maged SaeedMaged Saeed
8821417
answered Dec 16 '18 at 21:41
Maged SaeedMaged Saeed
8821417
answered Dec 16 '18 at 21:41
Maged SaeedMaged Saeed
8821417
8821417
1
$begingroup$
Thank you. I'll remember the second bullet point. This comes up a lot in my exercises...
$endgroup$
– thebilly
Dec 17 '18 at 7:10
add a comment |
1
$begingroup$
Thank you. I'll remember the second bullet point. This comes up a lot in my exercises...
$endgroup$
– thebilly
Dec 17 '18 at 7:10
1
1
$begingroup$
Thank you. I'll remember the second bullet point. This comes up a lot in my exercises...
$endgroup$
– thebilly
Dec 17 '18 at 7:10
$begingroup$
Thank you. I'll remember the second bullet point. This comes up a lot in my exercises...
$endgroup$
– thebilly
Dec 17 '18 at 7:10
add a comment |
draft saved
draft discarded
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%2f3042977%2fproof-by-induction-that-frac13n3-n-is-an-integer-am-i-on-the-correct-path%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$
Yeah I know, I forgot the induction hypothesis, but I just left it out, as those are just some exercises for myself, nothing I need to hand in...
$endgroup$
– thebilly
Dec 16 '18 at 18:41
$begingroup$
Since $n^2$ and $n$ are naturals, and naturals are closed under addition, we have the conclusion right?
$endgroup$
– Andrew Li
Dec 16 '18 at 18:45