Results 1 to 3 of 3

Math Help - Prove that every natural number is either even or odd?

  1. #1
    Member mfetch22's Avatar
    Joined
    Feb 2010
    From
    Columbus, Ohio, USA
    Posts
    168

    Prove that every natural number is either even or odd?

    This question is bugging me, and it has been for some time now. I know how to use mathematical induction, but I just dont see how I can "logically" fit it into this proof! I'm sure its oversight on my behalf.

    I know that every number can be written in the form 2n or 2n+1 and that 2n corresponds to all the even numbers and that 2n+1 corresponds to all the odd numbers. But, from my understanding mathematical induction works by steps, the whole 1 , 1+1, 1+1+1 , k, k+1 stuff, but how can I use induction on this problem? Because niether 2n or 2n+1 encompasses the whole set of positive numbers implied by induction, correct? Becuase in either set, they are missing "half" the numbers?

    How do you get around this and use induction (I'm sure, like I said, the answer is right under my nose, and is very obvious, but I'm just not seeing it), or any proof for that matter, to prove that evey natural number is either of the form 2n or 2n+1. Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Use strong induction. Break up your inductive step into two cases:  n is even and  n is odd.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148

    Form of integers.

    In PlanetMath: division algorithm for integers you can find a very short, useful information on the Division Algorithm.

    For any two integers a and b\neq 0, we can always a unique pair of integers q, r such that a=bq+r , with 0\leq  r<b. ( r is the remainder)

    In particular, choose b=2, then for any integer N , you have N=2n , or N=2n+1.

    From the Divistion Algorithm, we also know that any integer is exactly one of the forms 3n , 3n+1 , or 3n+2 .
    Last edited by melese; July 20th 2010 at 08:38 AM. Reason: I meant less than b.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: August 6th 2010, 10:54 AM
  2. Replies: 2
    Last Post: July 14th 2010, 02:16 PM
  3. Every natural number is sum of powers of 2
    Posted in the Number Theory Forum
    Replies: 23
    Last Post: January 13th 2010, 10:58 PM
  4. Replies: 6
    Last Post: May 26th 2009, 02:44 PM
  5. Prove natural number
    Posted in the Algebra Forum
    Replies: 3
    Last Post: April 25th 2009, 09:55 AM

Search Tags


/mathhelpforum @mathhelpforum