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

Basically, I tried proving that multiplying an odd and even number together gives you an even number to a friend of mine. This is what I said.

Let's first take a random number $k$. It doesn't matter if its odd or even. If we then multiply this by $2$, we get an even number (from the definition of a even number, which is basically a number that can be divided by $2$). Now we know that in the number line, it goes odd, even, odd, even,..., and so if we add $1$ to this, then we get an odd number. We now have an odd number and an even number and so lets multiply them.

$$2k \cdot (2k + 1) = 2k(2k + 1) = 4k^2 + 2k) = 2(2k^2 + k)$$

We now have a random number $(2k^2 + k)$ multiplied by $2$ and so this is an even number (by definition of an even number).

My friend then said that we make the assumption that $2k \pm 1$ is odd because the number line alternates between odd and even numbers, how do know that this is true?

I was thinking how to prove this. Would it be by some form of induction?

EDIT: I think I need to change "number" to "integer" in this post don't I?

-
You don't mean a random number, you just mean any integer. Random means something else. How do you define "odd" - is it just "not even," or is it something else? – Thomas Andrews Mar 6 '13 at 20:09
$2k$ and $2k+1$ are not arbitrary even and odd numbers, they are consecutive numbers. You really want to show it for $2k$ and $2l+1$. – Thomas Andrews Mar 6 '13 at 20:10
What does random mean? Ok, can I then say the definition of an odd integer is an integer that is not even, i.e an integer that when dividing by $2$ doesn't give you an integer. We can see that $2k + 1$ is odd as $\frac{2k + 1}{2} = \frac{2k}{2} + \frac{1}{2} = k + \frac{1}{2} = k.5$, which is not an integer as we have already defined $k$ to be one? – Kaish Mar 6 '13 at 20:12
But you really don't need it for this case. If $n=2k$ is any even integer, and $m$ is any integer, even or odd, then $nm=2(km)$ is even. The place where you need this is when showing that $nm$ is not even when $n,m$ are not even. – Thomas Andrews Mar 6 '13 at 20:34
You don't need to change "number." If you said "real number," it would be necessary, but "number" is fine when the context is clear, and, when talking even/odd, the context is always the integers or the natural numbers. – Thomas Andrews Mar 6 '13 at 21:24

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.

-
+1 because the proof really ought not be any more complicated than this, though I'd explicitly note the use of the associative property here. – Kyle Strand Mar 7 '13 at 7:52
+1 for clear and concise mathematical proof – Munim Mar 7 '13 at 8:04
This is clear and concise, but for rigor wouldn't you want to rely on the minimum number of definitions (axioms)? An even number is defined to be any integer of the form 2k (k=0 cannot be excluded), and an odd number is "everything else" (a member of the set of all integers that are not even). The proof would then need to derive the fact that all odd numbers are of the form 2k+1 - it seems like that should be simple, but as an engineer not a mathematician, I can't suggest how. – Dave Mar 7 '13 at 16:52
If we were to prove that all odd numbers are of the form 2k+1, I assume the easiest way is to use modulo arithmetic, so then we have that a even number is 0 modulo 2, so if a number is not even (and thus odd), it is 1 modulo 2, and thus of the form 2k+1 for some integer k. – Andrew D Mar 7 '13 at 17:22

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$

-
The choice of complete induction is merely because I was too lazy to rewrite it as induction after finishing. :-) – Asaf Karagila Mar 6 '13 at 20:23
Lol that's fine about induction. About your first "Lemma", can I "expand brackets" and say that in order for $2 \mid (a + 1)$, $(2 \mid a) + (2 \mid 1) = k, k \in \mathbb{Z}_+$, but from before we know that $2 \not \mid 1$ and so $2\not \mid(a + 1)$? Also you say that if $k$ is odd then $2 \not \mid k$, but can I again prove this from why a number is odd from my definition in the comments bit? – Kaish Mar 6 '13 at 20:26
You've just asserted that $2\not\mid 1$. That's requires proving too, when being pedantic. It's also related to the theorem that the only integers $r$ with $0\leq r<2$ are $r=0$ and $r=1$. That has to be proved, too. – Thomas Andrews Mar 6 '13 at 20:36
Also, OP defined "odd" as "not even," so your last two claims are redundant. – Thomas Andrews Mar 6 '13 at 20:38

You can prove by induction that all non-negative integers are of the form $2n$ or $2n+1$ for some $n$. Then you can prove it for negative integers, too.

That means that the integers which are not even are of the form $2n+1$.

-

Let $a$ be even.

Use the fact that $2\; \not \mid 1$. So if $2 \mid a$, (i.e., if a is even), $2 \not\mid (a + 1)$. Hence $a + 1$ is odd.

Then what about $(a + 1) + 1$, the number immediately following odd $(a + 1)$, which in turn immediately follows even $a$.

Well, $(a + 1) + 1 = a + 2$, and since $a$ is even, it can be expressed as $a = 2k$ for some integer $k$. Then $a + 2 = 2k + 2 = 2(k+1).$ And clearly, $2\mid 2(k+1).$

Hence, $a$ even $\implies (a + 1)$ odd $\implies (a + 2)$ even...

-

Note that by definition an integer $a\in{\mathbb{Z}}$ is odd if it is not divisible by two.
By Euclidean division we have that the remainder $r$ of the division by $2$ of any integer $n$ is such that $0 \leq r < 2$. Hence $n$ is either of the form $2k$ or $2k + 1$ for some $k\in{\mathbb{Z}}$.

-
One of the unsung elementary theorems of number theory is that there are no integers strictly between $0$ and $1$. Without it, you can't conclude the only possible values for $r$ are $0$ and $1$. – Thomas Andrews Mar 6 '13 at 20:32
How do you prove it? Doesn't it come for free from constructing the naturals by induction? – A.P. Mar 6 '13 at 20:45
You don't "construct" the integers by induction, induction is something you are allowed to use to prove things about the natural numbers. You do prove this statement by induction, but it isn't an axiom of the natural numbers. You first have to define $a<b$, of course, then prove by the above by induction. – Thomas Andrews Mar 6 '13 at 20:48
More formally, with "constructing the naturals by induction" I meant defining the naturals with a set-theoretical argument. The integers are then defined as the Grothendieck group of the naturals, but it is equivalent to prove this theorem for the integers or for the naturals. – A.P. Mar 6 '13 at 20:57
I wouldn't call what is done in set theory a construction, because, at least in ZF, it just asserts that a minimal infinite ordinal exists. I don't think one should have to go to a weird set-theory model for $\mathbb N$ to prove something that follows entirely from the Peano axioms. – Thomas Andrews Mar 6 '13 at 21:02

The parity of the sequence of naturals has period $\,2,\,$ since $\rm\,2\,$ divides $\rm\,n\!+\!2\,$ iff $\,2\,$ divides $\rm\,n.\:$ Further, successive numbers $\rm\,n,\,n\!+\!1\,$ have opposite parity, else $\,2\,$ would divide their difference $= 1.\:$ This explains your observed alternating pattern:  even, odd, even, odd, $\ldots,$ i.e. $\rm\ 0,1,0,1,\ldots (mod\ 2)$

Alternatively note that $\rm\ \ n\ mod\ 2\: =\: \dfrac{1-(-1)^n}2\$ has period $\,2\,$ since $\rm\,(-1)^n\,$ has period $\,2.$

-
+1 for the first proof, which is quite slick. You should have $(-1)^{n+1}$ in your second proof, though. – Kyle Strand Mar 7 '13 at 7:51
(Also, I just prefer the first proof generally because using the periodicity of an exponential function here seems like extreme overkill.) – Kyle Strand Mar 7 '13 at 7:52
@Kyle Thanks. I too prefer the first viewpoint. The formula in the second is correct. I added the second since, in some contexts, it might prove enlightening. – Math Gems Mar 7 '13 at 14:21
Oops, you're right; sorry. – Kyle Strand Mar 7 '13 at 17:33

As you say, even is a number divisible by 2. And if $a$ and $b$ are divisible by $d$, say, it means $a = d \cdot m$ and $b = d \cdot n$, so $a - b = d (m - n)$ is also divisible by $d$.

Now take $2 k + 1$, suppose it is divisible by 2. As $2 k$ is clearly divisible by $2$, if $2 k + 1$ is divisible by 2, then $1 = (2 k + 1) - 2 k$ is divisible by 2, and that is nonsense.

-

Let $m$ be an odd integer, and $n$ be an even integer.

Thus, by definition of odd and even, we have integers $k_1$ and $k_2$ such that: $$m = 2k_1 + 1$$ $$n = 2k_2$$

It follows that: \begin{align} m \cdot n &= (2k_1 + 1)\cdot(2k_2)\\ &= 4k_1k_2+2k_2 \\ &= 2(2k_1k_2 + k_2) \end{align}

As $(2k_1k_2 + k_2)$ is an integer, we have that $m\cdot n$ is even.

-

Induction is unnecessary for both the proof that the product of an odd integer and an even integer is even and the proof that the integers are alternately odd and even.

I like Thomas's proof of the multiplicative result (currently the highest-ranked answer), though I think it's important to explicitly point out that what we're relying on here is the associative property of multiplication. (This is important because not all multiplication-like operations in algebraic structures are associative.)

For the proof of alternating evens and odds, I would simply make the following observations:

Since "evenness" is defined as being divisible by 2, and "oddness" is defined as being not-even, all numbers are either even or odd.

Any even number $k$ can be represented as $2j$ for some integer $j$. Note that by the distributive property, $\frac{1}{2}(2j+1) = j + \frac{1}{2}$. Thus $k+1$ is not divisible by 2, and is therefore odd. Similarly, $k-1$ is odd.

Any odd number $n$ can be represented as $2i+1$ for some integer $i$. Note that $n-1 = 2i$, so $n$ is preceded by an even number. $n+1 = 2i+2 = 2(i+1)$, again by the distributive property, so $n$ is followed by an even number.

Therefore, every odd number is preceded and followed by an even number, and conversely, every even number is preceded and followed by an odd number. Thus the integers are alternately odd and even.

-
I am now wondering whether there exist non-associative rings such that repeatedly adding 1 to any element causes the result to alternate between being divisible by 2 and not being divisible by 2, but multiplying an element divisible by 2 with an element not divisible by 2 results in a product that is not divisible by 2. – Kyle Strand Mar 7 '13 at 7:46
A friend of mine who is not on math.stackexchange demonstrates that this is impossible by giving a proof that the product of even and odd numbers is always even regardless of whether your algebra is associative: $(2\cdot a)\cdot b = (a+a)\cdot b = a\cdot b + a\cdot b = (1+1)\cdot (a\cdot b) = 2\cdot (a\cdot b)$ – Kyle Strand Mar 7 '13 at 9:19
That is to say, the distributive property implies the associativity of multiplication involving 2. – Kyle Strand Mar 7 '13 at 9:21

Induction is unnecessary, the only requirement is associativity.

An even number is of the form 2k. For any j, the product (2k)j is of the form 2(kj).

Or in English, the product of an even number and any number is even. Therefore, the product of an even number and an odd number must be even.

-

$2k+1$ is odd because because 2 divides 2k and doesn't divide 1. An even number times an odd number is even because $2m\times (2n+1) = 4mn+2n = 2(2mn+n)$ which is even.

-