Show that $n^3-n$ is divisible by $6$ using induction












6












$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?










share|cite|improve this question











$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
















6












$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?










share|cite|improve this question











$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














6












6








6





$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?










share|cite|improve this question











$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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








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














  • 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










3 Answers
3






active

oldest

votes


















5












$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.






share|cite|improve this answer









$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





















2












$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






share|cite|improve this answer











$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



















1












$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$.






share|cite|improve this answer









$endgroup$













    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


















    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









    5












    $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.






    share|cite|improve this answer









    $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


















    5












    $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.






    share|cite|improve this answer









    $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
















    5












    5








    5





    $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.






    share|cite|improve this answer









    $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.







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    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
















    • 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













    2












    $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






    share|cite|improve this answer











    $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
















    2












    $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






    share|cite|improve this answer











    $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














    2












    2








    2





    $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






    share|cite|improve this answer











    $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







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    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


















    • $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











    1












    $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$.






    share|cite|improve this answer









    $endgroup$


















      1












      $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$.






      share|cite|improve this answer









      $endgroup$
















        1












        1








        1





        $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$.






        share|cite|improve this answer









        $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$.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Aug 1 '16 at 13:57









        Yves DaoustYves Daoust

        129k675227




        129k675227






























            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














            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





















































            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







            Popular posts from this blog

            Mont Emei

            Province de Neuquén

            Journaliste