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?
$\endgroup$ 811 Answers
$\begingroup$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.
$\endgroup$ 3 $\begingroup$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$
$\endgroup$ 4 $\begingroup$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$.
$\endgroup$ $\begingroup$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...
$\endgroup$ $\begingroup$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}}$.
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.$
$\endgroup$ 4 $\begingroup$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.
$\endgroup$ $\begingroup$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.
$\endgroup$ $\begingroup$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.
$\endgroup$ 3 $\begingroup$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.
$\endgroup$ $\begingroup$$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.
$\endgroup$
