Show that $n^3-n$ is divisible by $6$ using induction
$begingroup$
As homework, I have to prove that
$forall n in mathbb{N}: n^3-n$ is divisible by 6
I used induction
1) basis: $A(0): 0^3-0 = 6x$ , $x in mathbb{N}_0$ // the 6x states that the result is a multiple of 6, right?
2) requirement: $A(n):n^3-n=6x$
3) statement: $A(n+1): (n+1)^3-(n+1)=6x$
4) step: $n^3-n+(n+1)^3-n=6x+(n+1)^3-n$
So when I resolve that I do get the equation: $n^3-n=6x$ so the statement is true for $forall n in mathbb{N}$
Did I do something wrong or is it that simple?
induction divisibility
$endgroup$
add a comment |
$begingroup$
As homework, I have to prove that
$forall n in mathbb{N}: n^3-n$ is divisible by 6
I used induction
1) basis: $A(0): 0^3-0 = 6x$ , $x in mathbb{N}_0$ // the 6x states that the result is a multiple of 6, right?
2) requirement: $A(n):n^3-n=6x$
3) statement: $A(n+1): (n+1)^3-(n+1)=6x$
4) step: $n^3-n+(n+1)^3-n=6x+(n+1)^3-n$
So when I resolve that I do get the equation: $n^3-n=6x$ so the statement is true for $forall n in mathbb{N}$
Did I do something wrong or is it that simple?
induction divisibility
$endgroup$
1
$begingroup$
I know what you meant, but it's confusing when in both of steps (2) and (3) you use $6x$. It would be clearer if you had said in (2) $n^3-n=6x$ for some integer $x$ and in (3) you had said $(n+1)^3-(n+1)=6y$ for some integer $y$.
$endgroup$
– Rick Decker
Oct 11 '12 at 15:40
add a comment |
$begingroup$
As homework, I have to prove that
$forall n in mathbb{N}: n^3-n$ is divisible by 6
I used induction
1) basis: $A(0): 0^3-0 = 6x$ , $x in mathbb{N}_0$ // the 6x states that the result is a multiple of 6, right?
2) requirement: $A(n):n^3-n=6x$
3) statement: $A(n+1): (n+1)^3-(n+1)=6x$
4) step: $n^3-n+(n+1)^3-n=6x+(n+1)^3-n$
So when I resolve that I do get the equation: $n^3-n=6x$ so the statement is true for $forall n in mathbb{N}$
Did I do something wrong or is it that simple?
induction divisibility
$endgroup$
As homework, I have to prove that
$forall n in mathbb{N}: n^3-n$ is divisible by 6
I used induction
1) basis: $A(0): 0^3-0 = 6x$ , $x in mathbb{N}_0$ // the 6x states that the result is a multiple of 6, right?
2) requirement: $A(n):n^3-n=6x$
3) statement: $A(n+1): (n+1)^3-(n+1)=6x$
4) step: $n^3-n+(n+1)^3-n=6x+(n+1)^3-n$
So when I resolve that I do get the equation: $n^3-n=6x$ so the statement is true for $forall n in mathbb{N}$
Did I do something wrong or is it that simple?
induction divisibility
induction divisibility
edited Aug 1 '16 at 13:59
Rodrigo de Azevedo
13.1k41959
13.1k41959
asked Oct 11 '12 at 14:49
Marco RauscherMarco Rauscher
36112
36112
1
$begingroup$
I know what you meant, but it's confusing when in both of steps (2) and (3) you use $6x$. It would be clearer if you had said in (2) $n^3-n=6x$ for some integer $x$ and in (3) you had said $(n+1)^3-(n+1)=6y$ for some integer $y$.
$endgroup$
– Rick Decker
Oct 11 '12 at 15:40
add a comment |
1
$begingroup$
I know what you meant, but it's confusing when in both of steps (2) and (3) you use $6x$. It would be clearer if you had said in (2) $n^3-n=6x$ for some integer $x$ and in (3) you had said $(n+1)^3-(n+1)=6y$ for some integer $y$.
$endgroup$
– Rick Decker
Oct 11 '12 at 15:40
1
1
$begingroup$
I know what you meant, but it's confusing when in both of steps (2) and (3) you use $6x$. It would be clearer if you had said in (2) $n^3-n=6x$ for some integer $x$ and in (3) you had said $(n+1)^3-(n+1)=6y$ for some integer $y$.
$endgroup$
– Rick Decker
Oct 11 '12 at 15:40
$begingroup$
I know what you meant, but it's confusing when in both of steps (2) and (3) you use $6x$. It would be clearer if you had said in (2) $n^3-n=6x$ for some integer $x$ and in (3) you had said $(n+1)^3-(n+1)=6y$ for some integer $y$.
$endgroup$
– Rick Decker
Oct 11 '12 at 15:40
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
No, your argument is not quite right (or at least not clear to me). You must show that if $A(n)$ is true, then $A(n+1)$ follows. $A(n)$ here is the statement "$n^3-n$ is divisible by $6$". Assuming $A(n)$ is true, then
$$(n+1)^3-(n+1)=n^3+3n^2+3n+1-n-1=(n^3-n)+3n(n+1)$$
is divisible by $6$ because (1) $n^3-n$ is a multiple of $6$ by assumption, and (2) $3n(n+1)$ is divisible by $6$ because one of $n$ or $n+1$ must be even (this is related to what Alex was pointing out). Therefore $A(n)$ implies $A(n+1)$ and, if $A(n)$ is true for some value of $n$, then all higher integer values of $n$ follow. You correctly showed that $A(0)$ is true.
$endgroup$
2
$begingroup$
Of course, the argument that "one of $n$ or $n+1$ must be even" is no different from "one of $n, n-1, n+1$ must be divisible by 3". To stay within the spirit of the problem, the fact that $3n(n+1)$ is divisible by 6 should also be proved by induction.
$endgroup$
– mathguy
Aug 1 '16 at 13:33
add a comment |
$begingroup$
No need for induction.
$$n^3-n=n(n^2-1)=n(n-1)(n+1)$$
which are three consecutive integers. So one must be divisible by 3.
Check for $n=1$: $1^3-1=0=3cdot 0$
Assume it's true for $n=k$.
If you let $n=k+1$ you get
$$begin{align*}
(k+1)^3-(k+1)&=k^3+3k^2+2 \
&=k^3+3k^2+2k\
&=3cdot (k^2+k)+(k^3-k)end{align*}$$
which is divisible by 3
$endgroup$
$begingroup$
Thank you for your answer. I know that way, but I wanted to know if I used the principle of induction in the correct way.
$endgroup$
– Marco Rauscher
Oct 11 '12 at 14:54
$begingroup$
@Alex There is a need for induction if the question says "prove by induction" (as has been known to happen on a test).
$endgroup$
– yroc
Nov 23 '15 at 19:59
add a comment |
$begingroup$
If $n^3-n=6m$,
$$(n+1)^3-(n+1)=n^3+3n^2+2n=6m+3(n^2+n).$$
Then, by an auxiliary induction $n^2+n$ is even.
Indeed, $0^2+0$ is even and if $n^2+n=2k$,
$$(n+1)^2+(n+1)=n^2+3n+2=2k+2(n+1)$$ which is even.
Finally, $3$ times an even number is a multiple of $6$.
$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%2f211121%2fshow-that-n3-n-is-divisible-by-6-using-induction%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
No, your argument is not quite right (or at least not clear to me). You must show that if $A(n)$ is true, then $A(n+1)$ follows. $A(n)$ here is the statement "$n^3-n$ is divisible by $6$". Assuming $A(n)$ is true, then
$$(n+1)^3-(n+1)=n^3+3n^2+3n+1-n-1=(n^3-n)+3n(n+1)$$
is divisible by $6$ because (1) $n^3-n$ is a multiple of $6$ by assumption, and (2) $3n(n+1)$ is divisible by $6$ because one of $n$ or $n+1$ must be even (this is related to what Alex was pointing out). Therefore $A(n)$ implies $A(n+1)$ and, if $A(n)$ is true for some value of $n$, then all higher integer values of $n$ follow. You correctly showed that $A(0)$ is true.
$endgroup$
2
$begingroup$
Of course, the argument that "one of $n$ or $n+1$ must be even" is no different from "one of $n, n-1, n+1$ must be divisible by 3". To stay within the spirit of the problem, the fact that $3n(n+1)$ is divisible by 6 should also be proved by induction.
$endgroup$
– mathguy
Aug 1 '16 at 13:33
add a comment |
$begingroup$
No, your argument is not quite right (or at least not clear to me). You must show that if $A(n)$ is true, then $A(n+1)$ follows. $A(n)$ here is the statement "$n^3-n$ is divisible by $6$". Assuming $A(n)$ is true, then
$$(n+1)^3-(n+1)=n^3+3n^2+3n+1-n-1=(n^3-n)+3n(n+1)$$
is divisible by $6$ because (1) $n^3-n$ is a multiple of $6$ by assumption, and (2) $3n(n+1)$ is divisible by $6$ because one of $n$ or $n+1$ must be even (this is related to what Alex was pointing out). Therefore $A(n)$ implies $A(n+1)$ and, if $A(n)$ is true for some value of $n$, then all higher integer values of $n$ follow. You correctly showed that $A(0)$ is true.
$endgroup$
2
$begingroup$
Of course, the argument that "one of $n$ or $n+1$ must be even" is no different from "one of $n, n-1, n+1$ must be divisible by 3". To stay within the spirit of the problem, the fact that $3n(n+1)$ is divisible by 6 should also be proved by induction.
$endgroup$
– mathguy
Aug 1 '16 at 13:33
add a comment |
$begingroup$
No, your argument is not quite right (or at least not clear to me). You must show that if $A(n)$ is true, then $A(n+1)$ follows. $A(n)$ here is the statement "$n^3-n$ is divisible by $6$". Assuming $A(n)$ is true, then
$$(n+1)^3-(n+1)=n^3+3n^2+3n+1-n-1=(n^3-n)+3n(n+1)$$
is divisible by $6$ because (1) $n^3-n$ is a multiple of $6$ by assumption, and (2) $3n(n+1)$ is divisible by $6$ because one of $n$ or $n+1$ must be even (this is related to what Alex was pointing out). Therefore $A(n)$ implies $A(n+1)$ and, if $A(n)$ is true for some value of $n$, then all higher integer values of $n$ follow. You correctly showed that $A(0)$ is true.
$endgroup$
No, your argument is not quite right (or at least not clear to me). You must show that if $A(n)$ is true, then $A(n+1)$ follows. $A(n)$ here is the statement "$n^3-n$ is divisible by $6$". Assuming $A(n)$ is true, then
$$(n+1)^3-(n+1)=n^3+3n^2+3n+1-n-1=(n^3-n)+3n(n+1)$$
is divisible by $6$ because (1) $n^3-n$ is a multiple of $6$ by assumption, and (2) $3n(n+1)$ is divisible by $6$ because one of $n$ or $n+1$ must be even (this is related to what Alex was pointing out). Therefore $A(n)$ implies $A(n+1)$ and, if $A(n)$ is true for some value of $n$, then all higher integer values of $n$ follow. You correctly showed that $A(0)$ is true.
answered Oct 11 '12 at 14:58
JonathanJonathan
6,78511533
6,78511533
2
$begingroup$
Of course, the argument that "one of $n$ or $n+1$ must be even" is no different from "one of $n, n-1, n+1$ must be divisible by 3". To stay within the spirit of the problem, the fact that $3n(n+1)$ is divisible by 6 should also be proved by induction.
$endgroup$
– mathguy
Aug 1 '16 at 13:33
add a comment |
2
$begingroup$
Of course, the argument that "one of $n$ or $n+1$ must be even" is no different from "one of $n, n-1, n+1$ must be divisible by 3". To stay within the spirit of the problem, the fact that $3n(n+1)$ is divisible by 6 should also be proved by induction.
$endgroup$
– mathguy
Aug 1 '16 at 13:33
2
2
$begingroup$
Of course, the argument that "one of $n$ or $n+1$ must be even" is no different from "one of $n, n-1, n+1$ must be divisible by 3". To stay within the spirit of the problem, the fact that $3n(n+1)$ is divisible by 6 should also be proved by induction.
$endgroup$
– mathguy
Aug 1 '16 at 13:33
$begingroup$
Of course, the argument that "one of $n$ or $n+1$ must be even" is no different from "one of $n, n-1, n+1$ must be divisible by 3". To stay within the spirit of the problem, the fact that $3n(n+1)$ is divisible by 6 should also be proved by induction.
$endgroup$
– mathguy
Aug 1 '16 at 13:33
add a comment |
$begingroup$
No need for induction.
$$n^3-n=n(n^2-1)=n(n-1)(n+1)$$
which are three consecutive integers. So one must be divisible by 3.
Check for $n=1$: $1^3-1=0=3cdot 0$
Assume it's true for $n=k$.
If you let $n=k+1$ you get
$$begin{align*}
(k+1)^3-(k+1)&=k^3+3k^2+2 \
&=k^3+3k^2+2k\
&=3cdot (k^2+k)+(k^3-k)end{align*}$$
which is divisible by 3
$endgroup$
$begingroup$
Thank you for your answer. I know that way, but I wanted to know if I used the principle of induction in the correct way.
$endgroup$
– Marco Rauscher
Oct 11 '12 at 14:54
$begingroup$
@Alex There is a need for induction if the question says "prove by induction" (as has been known to happen on a test).
$endgroup$
– yroc
Nov 23 '15 at 19:59
add a comment |
$begingroup$
No need for induction.
$$n^3-n=n(n^2-1)=n(n-1)(n+1)$$
which are three consecutive integers. So one must be divisible by 3.
Check for $n=1$: $1^3-1=0=3cdot 0$
Assume it's true for $n=k$.
If you let $n=k+1$ you get
$$begin{align*}
(k+1)^3-(k+1)&=k^3+3k^2+2 \
&=k^3+3k^2+2k\
&=3cdot (k^2+k)+(k^3-k)end{align*}$$
which is divisible by 3
$endgroup$
$begingroup$
Thank you for your answer. I know that way, but I wanted to know if I used the principle of induction in the correct way.
$endgroup$
– Marco Rauscher
Oct 11 '12 at 14:54
$begingroup$
@Alex There is a need for induction if the question says "prove by induction" (as has been known to happen on a test).
$endgroup$
– yroc
Nov 23 '15 at 19:59
add a comment |
$begingroup$
No need for induction.
$$n^3-n=n(n^2-1)=n(n-1)(n+1)$$
which are three consecutive integers. So one must be divisible by 3.
Check for $n=1$: $1^3-1=0=3cdot 0$
Assume it's true for $n=k$.
If you let $n=k+1$ you get
$$begin{align*}
(k+1)^3-(k+1)&=k^3+3k^2+2 \
&=k^3+3k^2+2k\
&=3cdot (k^2+k)+(k^3-k)end{align*}$$
which is divisible by 3
$endgroup$
No need for induction.
$$n^3-n=n(n^2-1)=n(n-1)(n+1)$$
which are three consecutive integers. So one must be divisible by 3.
Check for $n=1$: $1^3-1=0=3cdot 0$
Assume it's true for $n=k$.
If you let $n=k+1$ you get
$$begin{align*}
(k+1)^3-(k+1)&=k^3+3k^2+2 \
&=k^3+3k^2+2k\
&=3cdot (k^2+k)+(k^3-k)end{align*}$$
which is divisible by 3
edited Oct 11 '12 at 15:00
answered Oct 11 '12 at 14:53
AlexAlex
2,131718
2,131718
$begingroup$
Thank you for your answer. I know that way, but I wanted to know if I used the principle of induction in the correct way.
$endgroup$
– Marco Rauscher
Oct 11 '12 at 14:54
$begingroup$
@Alex There is a need for induction if the question says "prove by induction" (as has been known to happen on a test).
$endgroup$
– yroc
Nov 23 '15 at 19:59
add a comment |
$begingroup$
Thank you for your answer. I know that way, but I wanted to know if I used the principle of induction in the correct way.
$endgroup$
– Marco Rauscher
Oct 11 '12 at 14:54
$begingroup$
@Alex There is a need for induction if the question says "prove by induction" (as has been known to happen on a test).
$endgroup$
– yroc
Nov 23 '15 at 19:59
$begingroup$
Thank you for your answer. I know that way, but I wanted to know if I used the principle of induction in the correct way.
$endgroup$
– Marco Rauscher
Oct 11 '12 at 14:54
$begingroup$
Thank you for your answer. I know that way, but I wanted to know if I used the principle of induction in the correct way.
$endgroup$
– Marco Rauscher
Oct 11 '12 at 14:54
$begingroup$
@Alex There is a need for induction if the question says "prove by induction" (as has been known to happen on a test).
$endgroup$
– yroc
Nov 23 '15 at 19:59
$begingroup$
@Alex There is a need for induction if the question says "prove by induction" (as has been known to happen on a test).
$endgroup$
– yroc
Nov 23 '15 at 19:59
add a comment |
$begingroup$
If $n^3-n=6m$,
$$(n+1)^3-(n+1)=n^3+3n^2+2n=6m+3(n^2+n).$$
Then, by an auxiliary induction $n^2+n$ is even.
Indeed, $0^2+0$ is even and if $n^2+n=2k$,
$$(n+1)^2+(n+1)=n^2+3n+2=2k+2(n+1)$$ which is even.
Finally, $3$ times an even number is a multiple of $6$.
$endgroup$
add a comment |
$begingroup$
If $n^3-n=6m$,
$$(n+1)^3-(n+1)=n^3+3n^2+2n=6m+3(n^2+n).$$
Then, by an auxiliary induction $n^2+n$ is even.
Indeed, $0^2+0$ is even and if $n^2+n=2k$,
$$(n+1)^2+(n+1)=n^2+3n+2=2k+2(n+1)$$ which is even.
Finally, $3$ times an even number is a multiple of $6$.
$endgroup$
add a comment |
$begingroup$
If $n^3-n=6m$,
$$(n+1)^3-(n+1)=n^3+3n^2+2n=6m+3(n^2+n).$$
Then, by an auxiliary induction $n^2+n$ is even.
Indeed, $0^2+0$ is even and if $n^2+n=2k$,
$$(n+1)^2+(n+1)=n^2+3n+2=2k+2(n+1)$$ which is even.
Finally, $3$ times an even number is a multiple of $6$.
$endgroup$
If $n^3-n=6m$,
$$(n+1)^3-(n+1)=n^3+3n^2+2n=6m+3(n^2+n).$$
Then, by an auxiliary induction $n^2+n$ is even.
Indeed, $0^2+0$ is even and if $n^2+n=2k$,
$$(n+1)^2+(n+1)=n^2+3n+2=2k+2(n+1)$$ which is even.
Finally, $3$ times an even number is a multiple of $6$.
answered Aug 1 '16 at 13:57
Yves DaoustYves Daoust
129k675227
129k675227
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%2f211121%2fshow-that-n3-n-is-divisible-by-6-using-induction%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$
I know what you meant, but it's confusing when in both of steps (2) and (3) you use $6x$. It would be clearer if you had said in (2) $n^3-n=6x$ for some integer $x$ and in (3) you had said $(n+1)^3-(n+1)=6y$ for some integer $y$.
$endgroup$
– Rick Decker
Oct 11 '12 at 15:40