Results 1 to 5 of 5
Like Tree1Thanks
  • 1 Post By Plato

Math Help - I need help understanding the basis of how proof work.

  1. #1
    Newbie
    Joined
    Mar 2011
    From
    GA
    Posts
    5

    I need help understanding the basis of how proof work.

    I missed the concept of "proofs" in highschool.
    I'm a programmer right now and something tells me they are valuable to my interest in pattern finding.

    I was reading this wiki page about basic proofs, but there is something I did not understand.
    It's extremely simple, I'm sure, but I don't want to jump to assumptions.
    So here it is
    "If x is odd (not even) then x = 2k + 1 for an integer k."
    Does this mean "make K any integer"? The language used isn't intuitive.
    Thanks for any help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,793
    Thanks
    1688
    Awards
    1

    Re: I need help understanding the basis of how proof work.

    Quote Originally Posted by Keysle View Post
    I was reading this wiki page about basic proofs, but there is something I did not understand.
    It's extremely simple, I'm sure, but I don't want to jump to assumptions.
    So here it is
    "If x is odd (not even) then x = 2k + 1 for an integer k."
    Does this mean "make K any integer"? The language used isn't intuitive.
    Thanks for any help.
    No, it does not mean that.
    If x is an odd integer, then x-1 is an even integer and hence divisible by two.

    So k=\frac{x-1}{2} is an integer. Thus x=2k+1.

    Therefore k is a particular integer.
    Thanks from Keysle
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2011
    From
    GA
    Posts
    5

    Re: I need help understanding the basis of how proof work.

    Sorry. I meant to put emphasis on the phrase "for an integer k.". For some reason it didn't accept my font alteration.

    edit ----------------
    Well apparently. on this computer it does show up. and now that I'm re-reading your comment. ...
    ...
    ...
    This is awfully confusing.
    Last edited by Keysle; June 5th 2012 at 07:17 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: I need help understanding the basis of how proof work.

    it means that there is at least one integer ("labelled" k, since we haven't determined it) with:

    x = 2k + 1.

    as stated, it could perhaps be that there are many such integers, although this is in fact not the case.

    for example, for x = 7, one such k is k = 3 (7 = 2(3) + 1).

    in the context of the wikipedia page, this may as well be taken as the definition of "oddness":

    an integer x is called odd if there is some other integer k with x = 2k+1. this is just a mathematical way of saying the odd integers are "in-between" the even ones, which are spaced 2 apart.

    often, in arguments about "evenness" and "oddness" (parity arguments), we don't need to know what "k" is. when you flip a switch, how many times you've flipped it is irrelevant, all that matters is its parity with the original state (from which you can tell the current state).

    given a certain odd integer x, you can use Plato's method to FIND k, if you know x. but if all you know is that x is odd, then k is just a (generic) integer. one can even state this as a theorem:

    for all integers k, 2k+1 is odd.

    proof (by induction):

    first suppose k is a natural number (which i will take as including 0).

    for k = 0, 2k+1 = 2(0) + 1 = 0 + 1 = 1. since 1/2 is not an integer, 1 is not divisible by 2, thus 1 is odd (not even).

    now suppose that 2k+1 is odd.

    if we can prove 2(k+1) + 1 = 2k + 2 + 1 = 2k + 3 is odd, we will have completed the "inductive step".

    but 2k + 3 = 2k + 2 + 1, so (2k + 3)/2 = (2k + 2)/2 + 1/2.

    if 2k + 3 is even, then (2k + 3)/2 is an integer, and since (2k + 2)/2 = k + 1, which is clearly an integer, we have that:

    1/2 = (2k + 3)/2 - (k + 1) is an integer, which is absurd. thus 2k + 3 must be odd (not even), so by the principle of induction, we conclude that 2k+1 is odd, for all natural numbers k.

    finally, if k < 0, then k = -m, for some positive integer m, and:

    2k + 1 = 2(-m) + 1 = -(2m - 1) = -(2(m-1) + 1).

    now m-1 is natural number (since k < 0, -k = m > 0, so m-1 ≥ 0), therefore by our above result: 2(m-1) + 1 is odd.

    so we only have to prove the following:

    if x is odd, so is -x.

    again, suppose -x is even, so -x/2 is an integer. since the negative of an integer is still an integer, x/2 is also an integer, so x is even. but this is absurd, as x is odd. thus -x cannot be even, so must be odd.

    the above discussion, together with Plato's post shows that saying:

    there exists an integer k such that x = 2k+1

    and:

    x is an odd integer

    are equivalent, each implies the other, and they can be used interchangeably.

    one can show easily that the "k" in x = 2k+1 is unique:

    suppose x = 2k+1 = 2m+1

    then 2k = 2m, so

    k = m (multiplication of integers is "cancellative").
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2011
    From
    GA
    Posts
    5

    Re: I need help understanding the basis of how proof work.

    Thanks. This helps wrap my head around the proof process.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help understanding basis and dimension
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 12th 2011, 04:23 AM
  2. Help understanding proof
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: November 9th 2010, 10:58 AM
  3. Basis of S - can someone please check my work
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 24th 2010, 05:21 PM
  4. Help Understanding a Proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: December 23rd 2009, 08:37 PM
  5. Understanding logic of proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 10th 2009, 09:33 AM

Search Tags


/mathhelpforum @mathhelpforum