Results 1 to 5 of 5

Math Help - Methods of Proof: Proof by Contrapositive

  1. #1
    Newbie
    Joined
    Oct 2012
    From
    USA
    Posts
    6

    Methods of Proof: Proof by Contrapositive

    THIS IS NOT HOMEWORK! This is a practice problem from our textbook. Class link: Discrete Math I
    Methods of Proof: Proof by Contrapositive-untitled-1.jpg
    Please correct if wrong:
    My solution:
    1) If n is odd, then n^2 is odd.
    2) Suppose that n=2a+1, where a is an arbitrary integer.
    3) Then n^2=(2a+1)^2 (Substitution)
    <=> (2a+1)(2a+1) (Distributive law)
    <=> 4a^2 + 4a + 1 (Distributive law, Associative law, Commutative law)
    <=> 2(2a^2 + 2a) + 1 (Distributive law)
    4) Since 2(2a^2 + 2a) + 1 = 2k + 1 (where k=2a^2 + 2a , and is therefore an integer) the proposition is true using the definition of odd: 2k + 1
    Last edited by sflink; October 28th 2012 at 04:50 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,607
    Thanks
    591

    Re: Methods of Proof: Proof by Contrapositive

    Hey sflink.

    You have show n implies n^2 but not the reverse.

    We know that a number is either even or odd and if it's not one then its the other. We know even^2 is even, but what about the reverse?

    Consider what happens when we multiply even*even and odd*odd. You can prove that even*even = even and odd*odd = odd for any odd numbers (even if they aren't the same necessarily). So this means odd*odd can't be even which means that if n = k*m and n is even then (k = ODD and m = ODD) can not occur. Similarly you have the same for even.

    You can do this formally by assuming its true and then come to a contradiction (proof by contradiction is the most powerful tool in mathematics).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,502
    Thanks
    765

    Re: Methods of Proof: Proof by Contrapositive

    Quote Originally Posted by chiro View Post
    You have show n implies n^2 but not the reverse.
    chiro, n cannot imply n^2 because both are numbers, not propositions. Also, I am not sure what the "reverse" is. An implication has the converse, the inverse and the contrapositive. The OP proved the claim correctly, using reasoning by contrapositive, as required. My only remarks are that it should be noted that 1) is the contrapositive of the claim that is going to be proved and that 2) marks the start of a proof. Also, the line after the first <=> is obtained not by the distributive law but by substitution, namely, of the definition of the squaring function (.)2 in terms of multiplication.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,607
    Thanks
    591

    Re: Methods of Proof: Proof by Contrapositive

    Thanks for that emakarov.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2012
    From
    USA
    Posts
    6

    Re: Methods of Proof: Proof by Contrapositive

    Sorry for the late reply. Thank you!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof by contrapositive help
    Posted in the Algebra Forum
    Replies: 3
    Last Post: October 18th 2012, 09:11 AM
  2. Proof by contrapositive
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 14th 2010, 03:45 PM
  3. contrapositive proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: May 5th 2010, 01:07 PM
  4. Contrapositive proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: September 27th 2009, 07:36 AM
  5. Proof by Contrapositive
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 13th 2009, 10:31 PM

Search Tags


/mathhelpforum @mathhelpforum