Results 1 to 7 of 7

Math Help - A simple proof, just want some checking!

  1. #1
    Newbie
    Joined
    Mar 2008
    Posts
    5

    A simple proof, just want some checking!

    I'm trying to get to grips with mathematical proofs. I think I almost have this, but am missing something.

    Q) Prove that if n=m^3-m, where m is an integer, then n is a multiple of 6.

    A) A proof by contradiction:
    Assume the inverse of the statement, that if n=m^3-m then n is not a multiple of 6.

    This implies that n = 6k +{1,2,3,4,5} where k is an integer. In other words, n has a remainder of between 1 and 5 if you try to divide it by 6.

    Now I need to show that this implies a contradiction with the original statement (n=m^3-m) for every case, {1,2,3,4,5}.

    Case 1: n = 6k+1
    By the orignal statement, this is equal to m^3-m. But m^3-m is always even, and 6k+1 is always odd. This is therefore obviously false. The same logic applies to cases 3 and 5.

    Case 2: n = 6k+2
    Again, by the original statement this is equal to m^3-m. But how do I show that this is false. This time both sides are even?

    This is where I get into trouble. I am a bit confused on how to prove that 6k+2=m^3-m leads to an obvious contradiction. I can see that you can disprove it by counter example: If k=1 then n=8, but m^3-m can only take values {0,0,6,24,...}. So in general, the statement is false. In fact, it is only true when the number we add on to 6k is 6, otherwise we always 'miss' the values that m^3-m can take. So I think I can see it in words, but how do I formulate it into a proper proof?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Q) Prove that if n=m^3-m, where m is an integer, then n is a multiple of 6.
    Base case 1 and 2

    6|(1^3-1) \iff 6|0

    6|(2^3-2) \iff 6|6

    assume n=k

    6|k^3-k

    Show k+1

    (k+1)^3-(k+1)=k^3+3k^2+3k+1-k-1=k^3-k+3k^2+3k=k^3-k+3k(k-1)

    Note that 6|(k^3-k) by hypothesis

    and 6|[3k(k-1)] because either k or k-1 is even.

    QED
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2008
    Posts
    5
    thank you, but although I see that you've written a recurrence relation for n, and tried to show that every term is a multiple of 6, does that really qualify as a proof in the strict mathematical sense? I understood that you must always assume the opposite of the given statement, then show this leads to a obviously false statement, such as 0=1. Otherwise you are just deriving implied relationships, not actually proving anything.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Quote Originally Posted by Rhetoric View Post
    thank you, but although I see that you've written a recurrence relation for n, and tried to show that every term is a multiple of 6, does that really qualify as a proof in the strict mathematical sense? I understood that you must always assume the opposite of the given statement, then show this leads to a obviously false statement, such as 0=1. Otherwise you are just deriving implied relationships, not actually proving anything.
    Proof by induction

    Show the base case.

    Assume n=k

    Prove k+1

    This shows that the statement is true for ALL integers.


    for example

    1+2+3+...n=\frac{n(n-1)}{2}

    This can be shown by induction to be true for all n
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Proof by contradiction is valid but is by no means the only way to prove something.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Mar 2008
    Posts
    5
    I see now, thanks.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Note that: n=m^3-m=m\cdot{(m^2-1)}=m\cdot{(m-1)\cdot{(m+1)}}

    That is, the product of 3 consecutive natural numbers. Now, given 2 consecutive numbers one of them must be divisble by 2, and given three consecutive natural numbers one must be divisible by 3. Thus the product is divisble by 6

    Or you can remember that n=m^3-m=m\cdot{(m-1)\cdot{(m+1)}}=6\cdot{\binom{m+1}{3}}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Cross checking a simple permutation problem
    Posted in the Statistics Forum
    Replies: 3
    Last Post: March 9th 2010, 07:58 PM
  2. Simple Differentiation (checking i'm right)
    Posted in the Calculus Forum
    Replies: 4
    Last Post: November 19th 2009, 12:34 AM
  3. Checking proof of atom
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: October 31st 2009, 06:19 AM
  4. Some revision needs checking - Simple questions.
    Posted in the Statistics Forum
    Replies: 3
    Last Post: August 6th 2009, 06:23 PM
  5. Proof Checking Help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 22nd 2009, 12:24 AM

Search Tags


/mathhelpforum @mathhelpforum