Results 1 to 3 of 3

Math Help - Proofs

  1. #1
    Member
    Joined
    May 2008
    Posts
    109

    Proofs

    Can someone point me in the direction of a good place to learn about proofs? I am starting a new chapter which is all about proofs and am stuck on the simplest of concepts:

    Prove that the square of an even number is an even number using:
    a direct proof
    an indirect proof
    a proof by contradiction

    They just get harder from here and I have never been good at proofs.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello again ^^

    Quote Originally Posted by sjenkins View Post
    Can someone point me in the direction of a good place to learn about proofs? I am starting a new chapter which is all about proofs and am stuck on the simplest of concepts:

    Prove that the square of an even number is an even number using:
    a direct proof
    P \Rightarrow Q
    This would be "if x is an even number, prove that x is an even number", using known facts.

    Hint : use x=2k.

    an indirect proof
    \overline{Q} \Rightarrow \overline{P}
    This would be "if x is an odd number, then x is an odd number".

    a proof by contradiction
    P \Rightarrow \overline{Q} \text{ : impossible.}
    If x is an even number, let's suppose that x is an odd number. Then, get to a contradiction


    I'm sorry I can't give you any book references for it, as I don't know anything about American or English litterature
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Reckoner's Avatar
    Joined
    May 2008
    From
    Baltimore, MD (USA)
    Posts
    1,024
    Thanks
    75
    Awards
    1

    Smile

    Quote Originally Posted by sjenkins View Post
    Can someone point me in the direction of a good place to learn about proofs? I am starting a new chapter which is all about proofs and am stuck on the simplest of concepts:

    Prove that the square of an even number is an even number using:
    a direct proof
    an indirect proof
    a proof by contradiction

    They just get harder from here and I have never been good at proofs.
    You should be able to find some good books on proofs. Look around a bit on Google or Amazon. This one by Eccles has a nice introduction. Perhaps others can give you more recommendations.

    For some examples:

    n\text{ is even }\Rightarrow n^2\text{ is even }

    Direct: We form a chain of implications, starting with our given and ending with our desired result:

    n\text{ is even } (Given)

    \Rightarrow n = 2q,\;q\in\mathbb{Z} (By definition of an even number)

    \Rightarrow n^2 = (2q)^2 (Squaring both sides)

    \Rightarrow n^2 = 4q^2 (Expanding)

    \Rightarrow n^2 = 2(2q^2) (Factoring out a 2)

    \Rightarrow n^2 = 2p,\;p=2q^2\in\mathbb{Z}

    \Rightarrow n^2\text{ is even } (By definition)

    Therefore, n\text{ is even }\Rightarrow n^2\text{ is even }\qquad\square

    Then you could put the proof in a more presentable form by cutting out any unnecessary explanatory comments and tidying it up into a nice paragraph.



    Indirect: Let's prove the contrapositive (i.e. p\Rightarrow q and \lnot q\Rightarrow\lnot p are logically equivalent statements). So, we show that n^2\text{ is odd}\Rightarrow n\text{ is odd}.

    n^2\text{ is odd}

    \Rightarrow 2 does not divide n^2

    \Rightarrow 2 does not divide any factor of n^2

    \Rightarrow 2 does not divide n

    \Rightarrow n\text{ is odd}

    Thus n^2\text{ is odd}\Rightarrow n\text{ is odd}, and it follows that n\text{ is even }\Rightarrow n^2\text{ is even }\qquad\square



    Contradiction: Let's assume that our result is false, and show that such an assumption would lead to a contradiction.

    Assume the contrary, and suppose there is some integer n which is even and for which n^2 is odd.

    Since n is even, n = 2p,\;p\in\mathbb{Z}

    \Rightarrow n^2 = 2pn

    \Rightarrow 2|n^2 (since pn is an integer)

    \Rightarrow n^2\text{ is even}

    But, by our assumption, n^2 is also odd, which is a contradiction. Thus our assumption that there is an even integer whose square is odd must be false, and

    n\text{ is even }\Rightarrow n^2\text{ is even }\qquad\square
    Last edited by Reckoner; June 22nd 2008 at 03:23 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proofs
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 2nd 2010, 03:54 AM
  2. lim sup and lim inf proofs
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: February 24th 2010, 07:02 PM
  3. More Proofs
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 13th 2008, 07:05 PM
  4. Proofs
    Posted in the Calculus Forum
    Replies: 1
    Last Post: February 3rd 2008, 04:23 AM
  5. Replies: 3
    Last Post: October 6th 2007, 02:01 PM

Search Tags


/mathhelpforum @mathhelpforum