# Thread: Proove: the sum of two even numbers is even

1. ## Proove: the sum of two even numbers is even

$\displaystyle E:= \{m: 2m, m \in \mathbb{N}\}$

$\displaystyle U:= \{n: 2n+1, n \in \mathbb{N}\}$

Proof by contradiction:
assume $\displaystyle E_1+E_2=U$

$\displaystyle \Rightarrow 2m_1+2m_2=2n+1$

$\displaystyle \Rightarrow 2m_1+2m_2-1=2n$

$\displaystyle \Rightarrow \nexists m \in \mathbb{N}: 2\mid(2m_1+2m_2-1)$

This contradicts the assumption, therefore E_1 + E_2 = E_3

2. Isn't 2m+ 2n= 2(m+n) simpler?

3. Hello bmp05
Originally Posted by bmp05
$\displaystyle E:= \{m: 2m, m \in \mathbb{N}\}$

$\displaystyle U:= \{n: 2n+1, n \in \mathbb{N}\}$

Proof by contradiction:
assume $\displaystyle E_1+E_2=U$

$\displaystyle \Rightarrow 2m_1+2m_2=2n+1$

$\displaystyle \Rightarrow 2m_1+2m_2-1=2n$

$\displaystyle \Rightarrow \nexists m \in \mathbb{N}: 2\mid(2m_1+2m_2-1)$

This contradicts the assumption, therefore E_1 + E_2 = E_3
Are you required to prove this by contradiction? The direct proof is very straightforward. We define an even number in the obvious way: $\displaystyle n$ is even $\displaystyle \iff \exists \,m \in \mathbb{N}, n = 2m$.

Then $\displaystyle n_1$ is even and $\displaystyle n_2$ is even $\displaystyle \Rightarrow \exists \,m_1, m_2 \in \mathbb{N}, (n_1 = 2m_1) \wedge (n_2 = 2m_2)$

$\displaystyle \Rightarrow n_1 + n_2 = 2m_1 + 2m_2 = 2(m_1+m_2)$

$\displaystyle \Rightarrow n_1 + n_2$ is even

If you're going to use a 'contradiction' method, I think you have to be a little more careful with your use of notation. The definition of your sets should be

$\displaystyle E = \{m:m=2n, n \in \mathbb{N}\}$

$\displaystyle U = \{m:m=2n+1, n \in \mathbb{N}\}$

Then your hypothesis would be:

Assume $\displaystyle \exists\,m_1, m_2 \in E, m_1 + m_2 =m_3, m_3\in U$

Then $\displaystyle \exists\, n_1, n_2,n_3\in \mathbb{N},m_1=2n_1, m_2 = 2n_2, m_3 = 2n_3+1$

$\displaystyle \Rightarrow 2n_1+2n_2 = 2n_3+1$

$\displaystyle \Rightarrow 2(n_1+n_2 -n_3)=1$

$\displaystyle \Rightarrow 2 |1$. Contradiction.

Grandad

4. Thanks grandad! I was trying to follow your last example as well, btw. I read that you should be careful to not neglect the direct proof, because it is easier if possible, but then I have hardly ever seen it used.

5. And now to prove uneven.even = even

$\displaystyle n$ is even $\displaystyle \iff \exists \,m \in \mathbb{N}, n = 2m$.
$\displaystyle i$ is uneven $\displaystyle \iff \exists \,m \in \mathbb{N}, i = 2m+1$.

Then $\displaystyle n$ is even and $\displaystyle i$ is uneven $\displaystyle \Rightarrow \exists \,m_1, m_2 \in \mathbb{N}, (n = 2m_1) \wedge (i = 2m_2+1)$

$\displaystyle \Rightarrow n.i = 2m_1 . (2m_2+1) = 2m_1.2m_2+2m_1 = 2.m_1(m_2+1)$

$\displaystyle \Rightarrow n.i$ is even

Is this a trivial case, because you prove that $\displaystyle 2 \mid P(n)$ but $\displaystyle P(n) is 2m.n$ using the definition of an even number? (But that's the same for adding two even numbers as well...)

6. Hello bmp05
Originally Posted by bmp05
And now to prove uneven.even = even

$\displaystyle n$ is even $\displaystyle \iff \exists \,m \in \mathbb{N}, n = 2m$.
$\displaystyle i$ is uneven $\displaystyle \iff \exists \,m \in \mathbb{N}, i = 2m+1$.

Then $\displaystyle n$ is even and $\displaystyle i$ is uneven $\displaystyle \Rightarrow \exists \,m_1, m_2 \in \mathbb{N}, (n = 2m_1) \wedge (i = 2m_2+1)$

$\displaystyle \Rightarrow n.i = 2m_1 . (2m_2+1) = 2m_1.2m_2+2m_1 = \color{red}2.m_1(m_2+1)$

$\displaystyle \Rightarrow n.i$ is even

Is this a trivial case, because you prove that $\displaystyle 2 \mid P(n)$ but $\displaystyle P(n) is 2m.n$ using the definition of an even number? (But that's the same for adding two even numbers as well...)
Well done. You've got this pretty well complete, except for the bit I've marked in red, where you've just gone back to the original expression.

I agree, it does look more or less trivial, but what you should have said is

$\displaystyle \Rightarrow n.i = 2m_1 . (2m_2+1) = 2 \color{red}\times (2m_1m_2+m_1)$

which is now in the format $\displaystyle 2 \color{red}\times p\color{black}, p\in \mathbb{N}$

So that you can now say:

$\displaystyle \Rightarrow n.i$ is even

using the $\displaystyle \color{red}\Leftarrow$ part of the definition that $\displaystyle n$ is even $\displaystyle \color{red}\iff\color{black} \exists \,m \in \mathbb{N}, n = 2m$

Do you understand this subtle, but important, point?

Grandad

7. Yes- thanks again, I realised that I needed to show something analogue to the definition of the even number, but I can see that it is much clearer to substitute of the natural numbers $\displaystyle (m_1.m_2+m_1)$ as opposed to $\displaystyle m_1(m_2+1)$. But the most important thing missing from the proof is this substitution of an equivalent natural number p.
This reminds me of another probelm that I'm having proving the distributive laws in set theory- it is somehow simple, but hard to express in the right way!

Proove $\displaystyle \forall k \in \mathbb{Z}: 3 \mid k \Leftrightarrow 3 \mid k^2$

$\displaystyle \equiv (3 \mid k \Rightarrow 3 \mid k^2) \wedge (3 \mid k^2 \Rightarrow 3 \mid k)$

Part1: $\displaystyle 3 \mid k \Rightarrow 3 \mid k^2$

$\displaystyle 3 \mid k \Leftrightarrow k = 3.l,$ $\displaystyle k,l \in \mathbb{Z}$

$\displaystyle \Rightarrow k^2 = (3.l)^2 = 3.(3.l^2)$

$\displaystyle \exists p \in \mathbb{Z}: p = (3.l^2)$

$\displaystyle \Rightarrow 3.(3.l^2) = 3.p$

$\displaystyle \Rightarrow 3 \mid k \Rightarrow 3 \mid k^2$

Part2: $\displaystyle 3 \mid k^2 \Rightarrow 3 \mid k$

$\displaystyle 3 \mid k^2 \Leftrightarrow k^2=3.l,$ $\displaystyle k,l \in \mathbb{Z}$

$\displaystyle 3 \mid k \Leftrightarrow k = 3.m, k,m \in \mathbb{Z}$

$\displaystyle \exists m \in \mathbb{Z} : m=l$

$\displaystyle \Rightarrow 3.l \Rightarrow 3.m$

$\displaystyle 3 \mid k^2 \Rightarrow 3 \mid k$

It follows that, $\displaystyle (3 \mid k \Rightarrow 3 \mid k^2) \wedge (3 \mid k^2 \Rightarrow 3 \mid k)$

$\displaystyle \forall k \in \mathbb{Z}: 3 \mid k \Leftrightarrow 3 \mid k^2$

Unfortunately, it's not very clear to read.

8. Hello bmp05
Part1: $\displaystyle 3 \mid k \Rightarrow 3 \mid k^2$

$\displaystyle 3 \mid k \Leftrightarrow k = 3.l,$ $\displaystyle k,l \in \mathbb{Z}$

$\displaystyle \Rightarrow k^2 = (3.l)^2 = 3.(3.l^2)$

$\displaystyle \exists p \in \mathbb{Z}: p = (3.l^2)$

$\displaystyle \Rightarrow 3.(3.l^2) = 3.p$

$\displaystyle \Rightarrow 3 \mid k \Rightarrow 3 \mid k^2$
Part 1 of your proof is fine.
Part2: $\displaystyle 3 \mid k^2 \Rightarrow 3 \mid k$

$\displaystyle 3 \mid k^2 \Leftrightarrow k^2=3.l,$ $\displaystyle k,l \in \mathbb{Z}$

$\displaystyle 3 \mid k \Leftrightarrow k = 3.m, k,m \in \mathbb{Z}$

$\displaystyle \exists m \in \mathbb{Z} : m=l$

$\displaystyle \Rightarrow 3.l \Rightarrow 3.m$

$\displaystyle 3 \mid k^2 \Rightarrow 3 \mid k$
This is not so good. One way to check to see if it makes sense is this: $\displaystyle p|k^2 \Rightarrow p|k$ only works if $\displaystyle p$ is a prime number, or a product of single powers of prime numbers. (For instance, $\displaystyle 3|36 \Rightarrow 3|6$ is OK, but $\displaystyle 4|36 \Rightarrow 4|6$ isn't.) But you haven't used the fact anywhere in your proof that 3 is a prime.

You need to use the Fundamental Theorem of Arithmetic and say that if
$\displaystyle k=\prod p_i^{r_i}$, where the $\displaystyle p_i$ are primes, then $\displaystyle k^2=\prod p_i^{r_i}\times\prod p_i^{r_i}=\prod p_i^{2r_i}$. So $\displaystyle 3|k^2 \Rightarrow 3 = p_i$, for some $\displaystyle i$, and therefore $\displaystyle 3 | k$.

Grandad

9. Hello Grandad,
I'm not sure about the Fundamental Theorem of Arithmetic, I had a look at the wikipedia page and it looks interesting, but the course is moving very quickly, unfortunately and although I can't write very good proofs yet, we have already moved onto fields (help!)- anyway, I thought of a good idea for this problem, but I'm not sure how to proove it.
The idea is that $\displaystyle \forall k \in \mathbb{Z},~k = 3m,~3m+1,~3m+2, ~m \in \mathbb{Z}$
This would mean that I can jump straight into the $\displaystyle 3 | k^2 \Rightarrow 3 | k$ proof, because $\displaystyle k^2$ can only ever equal one of the 3 possibilities above. But the proof becomes something like:

$\displaystyle \forall k \in \mathbb{Z},~(k=3m)~\vee~(k=3m+1)~\vee~(k=3m+2)$, so I would like to say something like:

Proof by contraditiction, suppose $\displaystyle k = 3m+1~~or~~k = 3m+2$

$\displaystyle \Rightarrow k^2~= (3m+1)^2~~or~~(3m+2)^2$

$\displaystyle \Rightarrow k^2~=(9m^2 + 6m + 1)~~or~~(9m^2 + 12m + 4)$

$\displaystyle \Rightarrow 3 \mid (9m^2 + 6m + 1)~~or~~3 \mid (9m^2 + 12m + 4)$

[Errr... well, I- this seems to be true, but I don't know how to...?]

$\displaystyle \Rightarrow (9m^2 + 6m + 1) = 3 . n,~~\exists~n \in \mathbb{Z}$

$\displaystyle \Rightarrow 3m^2 + 2m + \frac{1}{3} = n$

[... do the same for the other or]

This is a contradiction, therefore $\displaystyle 3 \mid k^2 \Leftrightarrow 3 \mid k$

Well, this is a terrible proof, but on the good side, if done correctly this would actually be an "if and only if" proof! (?)

10. Hello bmp05

Well done. I think this is pretty well OK. I should just change the last part a bit (the part where you weren't so sure) so that instead of:
Originally Posted by bmp05
$\displaystyle \Rightarrow (9m^2 + 6m + 1) = 3 . n,~~\exists~n \in \mathbb{Z}$

$\displaystyle \Rightarrow 3m^2 + 2m + \frac{1}{3} = n$

This is a contradiction, therefore $\displaystyle 3 \mid k^2 \Leftrightarrow 3 \mid k$
I think I'd factorise the right-hand sides, and say:

$\displaystyle 3 \mid (9m^2 + 6m + 1)~~or~~3 \mid (9m^2 + 12m + 4)$

$\displaystyle \Rightarrow 3 \mid 3(3m^2 + 2m) + 1~~or~~3\mid 3(3m^2 + 4m + 1) + 1$

Contradiction, since $\displaystyle 3(3m^2 + 2m) + 1$ and $\displaystyle 3(3m^2 + 4m + 1) + 1$ both leave remainder $\displaystyle 1$ when divided by $\displaystyle 3$.

Grandad

11. Mathematics, or how to complicate simple things