Hello, I'm re-studying calculus using Spivak's Calculus 4ed and I'm stuck in one of the problems. Any help is appreciated. 1. The problem statement, all variables and given/known data The theorem to prove is "every natural number is either even or odd". The definition of even given by Spivak is the following: A natural number n is even if there exists an integer k such that n = 2k. Similarly, for an odd natural number n, there exists an integer k such that 2 = 2k+1. I can also use the basic facts about natural numbers and integers, such as associativity, commutativity, existence of identity, and distributivity. The other property of the natural numbers I can use is the principle of mathematical induction. 2. The attempt at a solution First, my understanding of the "either or" is that I must prove that every natural n is even or odd _and not both_. A general argument by induction will look like: The number 1 is odd because there exists a k = 0, such that 2*0 + 1 = 1 Suppose n is either even or odd. If even then there exists a k such that n = 2k, and n+1 = 2k+1 and so, n+1 is odd. The case for n odd is similar. And so, if n is even or odd, then n+1 is even or odd. By the principle of mathematical induction, all natural numbers are even or odd. The problem (one of the problems?) with this proof is that I don't show that a natural number can't be even and odd at the same time. I can't even start to show that 1 is not even. I need to prove that there are no integer k such that 1 = 2k. I understand that the only "number" that satisfy the equation is 1/2 and 1/2 is not an integer, but I can't state that in a proof with the principles that were given. Any help? :) Thanks!