How do we know all numbers alternate between odd and even numbers?

Solution 1:

I wouldn't appeal to the fact that the integers alternate between even and odd.

I would say this:

An even number is defined as any integer of the form $2k$ for $k$ any integer (maybe excluding $k=0$).

An odd number is defined as any integer of the form $2k +1$ for any integer $k$.

You can just take this as the definition. And then (as you have) the proof that even times odd is even is just $$ 2k(2k'+1) = 2[k(2k'+1)] $$ where of course $k(2k'+1)$ is just an integer.

Solution 2:

Yes, you can prove this by induction.

Claim. $2\nmid 1$.

Proof. For positive integers, it holds that $k\mid n$ implies $k\leq n$, since $1<2$, we have that $2\nmid 1$. Furthermore, $1$ is the successor of $0$ and $2$ is the successor of $1$, therefore the only non-negative numbers smaller than $2$ are $0,1$ and so they are the only possible remainders when dividing a positive integer $k$ by $2$. $\square$

Lemma. If $k$ is even then $k+1$ is odd, and if $k$ is odd then $k+1$ is even.

Proof. If $k$ is even then $2\mid k$, and then $2\nmid k+1$ because $2\nmid 1$; therefore $k+1$ is odd. If $k$ is odd then $2\nmid k$ and so the remainder of $k$ when divided by $2$ is $1$, so $2\mid k+1$, and it is even. $\square$

Claim. Every $n\in\Bbb N$ is either odd or even.

Proof. We prove using complete induction. Suppose that for every $k<n$ either $k$ is odd or $k$ is even. In particular this is true for $k=n-1$. If $k$ is even then $k+1=n$ is odd; and if $k$ is odd then $k+1$ is even. $\square$

Claim. Every $k\in\Bbb Z$ is either odd or even.

Proof. By the above claim it holds for $k\geq 0$, and $2\mid k\iff 2\mid -k$, so the claim holds for every integer. $\square$