Results 1 to 3 of 3

Thread: 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
    $\displaystyle 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
    $\displaystyle \overline{Q} \Rightarrow \overline{P}$
    This would be "if x is an odd number, then x is an odd number".

    a proof by contradiction
    $\displaystyle 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
    76
    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:

    $\displaystyle 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:

    $\displaystyle n\text{ is even }$ (Given)

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

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

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

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

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

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

    Therefore, $\displaystyle 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. $\displaystyle p\Rightarrow q$ and $\displaystyle \lnot q\Rightarrow\lnot p$ are logically equivalent statements). So, we show that $\displaystyle n^2\text{ is odd}\Rightarrow n\text{ is odd}.$

    $\displaystyle n^2\text{ is odd}$

    $\displaystyle \Rightarrow$ 2 does not divide $\displaystyle n^2$

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

    $\displaystyle \Rightarrow$ 2 does not divide $\displaystyle n$

    $\displaystyle \Rightarrow n\text{ is odd}$

    Thus $\displaystyle n^2\text{ is odd}\Rightarrow n\text{ is odd}$, and it follows that $\displaystyle 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 $\displaystyle n$ which is even and for which $\displaystyle n^2$ is odd.

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

    $\displaystyle \Rightarrow n^2 = 2pn$

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

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

    But, by our assumption, $\displaystyle 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

    $\displaystyle n\text{ is even }\Rightarrow n^2\text{ is even }\qquad\square$
    Last edited by Reckoner; Jun 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: Mar 2nd 2010, 03:54 AM
  2. lim sup and lim inf proofs
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: Feb 24th 2010, 07:02 PM
  3. More Proofs
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Feb 13th 2008, 07:05 PM
  4. Proofs
    Posted in the Calculus Forum
    Replies: 1
    Last Post: Feb 3rd 2008, 04:23 AM
  5. Replies: 3
    Last Post: Oct 6th 2007, 02:01 PM

Search Tags


/mathhelpforum @mathhelpforum