Prove that every natural number is either even or odd using induction

Question

It is a pretty basic question at first sight. It seems to be intuitively correct but I can't figure out a way to prove it. I think we have to use strong induction but even after sitting on this question for a long time, I still haven't got any leads.

Answer 1

Define an even number as a multiple of 2, and an odd number as a multiple of 2 plus 1.

Induction. Your inductive hypothesis is $H_n$: the positive integer $n$ is even or odd. $H_1$ is true, because 1 is a multiple of 2 plus 1. Suppose $H_n$ is true. Then either (i) $n$ is a multiple of 2 or (ii) $n$ is a multiple of 2 plus 1. In case (i), $n+1$ is a multiple of 2 plus 1; in case (ii) $n+1$ is a multiple of 2. So in both cases $H_{n+1}$ is true. So $H_n$ is true for all positive integers $n$.

Answer 2

Alternative approach:

For positive integer $n$,
$n$ is odd $\iff 2|(n+1)~$ and
$n$ is even $\iff 2|n.$

$1$ is odd and $2$ is even.

Inductively assume that $(n+1)$ is odd and $(n+2)$ is even.

Then, $2|([n+1] + 1) \implies 2|([n+3] + 1) \implies (n+3)$ is odd.

Thus, $(n+1)$ is odd $\implies (n+3)$ is odd.

By virtually identical analysis, $(n+2)$ even $\implies (n+4)$ even.

Therefore, you have the base cases of $1$ odd, $2$ even and, by inductive analysis, whenever $(n+1)$ is odd, so is $(n+3)$ and whenever $(n+2)$ is even, so is $(n+4).$

Answer 3

Base case: $0$ is even since $0 = 2 \times 0$.

Assumption: Assume that $n \in \mathbb{Z}$ is even or odd. Hence, $n=2k$ or $n=2k+1$ with $k \in \mathbb{Z}$.

Inductive step: If $n$ is even, then $n=2k$ with $k \in \mathbb{Z}$. Adding one to both sides of the equality, we find that $n+1=2k+1$ (i.e. $n$ is odd). Hence, if $n$ is even, then $n+1$ is odd.* If $n$ is odd, then $n=2k+1$ with $k \in \mathbb{Z}$. Adding one to both sides of the equality, we find that $n+1=2k+2=2(k+1)$. Since $n+1$ is the product of $2$ and an integer, $n+1$ is even.** Therefore, regardless of whether $n$ is even or odd, $n+1$ is even or odd.

Hence, if the statement is true for $n$, then it is true for $n+1$. Since the statement is true for $n=0$, it must be true for all $n \in \mathbb{N}$ by mathematical induction.

---

*We have actually proven the stronger result that if $n$ is even, then $n+1$ is odd, but this is not strictly necessary for the proof.

**This actually assumes that if $k$ is an integer, then $k+1$ is an integer. This fact is often adopted as an axiom.

Answer 4

The induction proof will be a lot easier to understand if the 'odd' and 'even' aspect is made algebraic from the outset.

Theorem

Every natural number is of the form $2k$ or $2k+1$ for some integer $k$.

Proof

The first natural number, $1$, is of the form $2\times 0+1$.

Suppose the theorem to be true for the natural number $n$. Then $n$ is either $2k$ or $2k+1$.

Then $n+1$ is either $2k+1$ or $2k+2=2(k+1)$. Hence the theorem is true for the natural number $n+1$.

By induction the theorem is true for all natural numbers.