# prove: if n is even, then n+1 is not even

This proof seems so simple that it's hard (if that makes any sense.)

based on the definition, n is even iff there exists k such that n = 2k.

What I really want to say is (big picture)

By definition, let $n = 2k.\;$ Then $n+1 = 2k + 1$.

$2k + 1$ is not divisible by $2$, therefore $n + 1$ is not even.

I can't seem to figure out how to show the work. Any help would be appreciated.

-

I love contradiction. Here is how I would do it:

Let n and n+1 both be even,

Therefore, $n=2k$ for some k and $n+1=2j$ for some $j,k \in \mathbb{I}$

Subtracting, $n+1-n=2j-2k$. $$1 = 2(j-k)$$ $$\frac{1}{2} = j-k$$ But, 1<2 so, the fraction is not an integer and the difference of 2 integers is necessarily an integer. Thus, Contradiction!

-
Perhaps it should be mentioned explicitly that $\frac{1}{2}$ is not an integer because $1 < 2$. If I'm really committed to the idea that $1$ might be even, I might not see a contradiction in $\frac{1}{2}$ being an integer. – Austin Mohr Nov 10 '12 at 19:48
The difference of 2 integers cannot be a fraction? I would have sworn that the difference of 7 and 9 equals $\frac63$. (So what it boils down to is how do you know $1$ is not even)? – Henning Makholm Nov 10 '12 at 19:48
simply say the difference of two integers can not be in the interval $]0,1[$. – user31280 Nov 10 '12 at 19:51
@F'Ola: But again, how do you know that? – Henning Makholm Nov 10 '12 at 19:52
@Inquest Every time you write a sentence, ask yourself if you can prove it. If you can't, either you've caught a mistake or you've found a chance to learn something new, both of which are positive outcomes. – Austin Mohr Nov 10 '12 at 22:04

You'd need to add a step to relate to your definition of even number.

Suppose $2k+1$ is even. then there exist some $k_1$ such that $2k+1=2k_1$. What does this mean?

Well if that is the case, then simple algebric manipulations get us to $$1=2(k_1-k)$$ which means $(k_1-k)=1/2$. But $k,k_1$ are integers, and $1/2$ is not, $1$ being smaller than $2$. We get a contradiction.

-
What a coincidence. – Inquest Nov 10 '12 at 19:44
Indeed +1 to you – Jean-Sébastien Nov 10 '12 at 19:44
Perhaps it should be mentioned explicitly that $\frac{1}{2}$ is not an integer because $1 < 2$. If I'm really committed to the idea that $1$ might be even, I might not see a contradiction in $\frac{1}{2}$ being an integer. – Austin Mohr Nov 10 '12 at 19:47
@AustinMohr done – Jean-Sébastien Nov 10 '12 at 19:50

For a given pair of even numbers $2a>2b$ it is the case that $2a-2b=2(a-b)$. Thus the difference between two even numbers is even. However, the difference between $n$ and $n+1$ is $1$, which is not an even number. Thus it cannot be the case that both $n$ and $n+1$ are even.

This is a slightly different take that proves that, in general, no two consecutive numbers can be even.

-

What's missing so far is a rigorous proof that $1$ is not even. Here is one that starts from the Peano arithmetic.

Suppose $1=S(0)$ is even. That means that for some $a$ we have that $S(0)=a+a$. Now either $a=0$ or $a=S(b)$ for some $b$. (This can be proved by induction on $a$ if you don't already know it).

In the case where $a=0$, we have $S(0)=0+0=0$, but $S(x)\ne 0$ for all $x$ by axiom, so this is a contradiction.

On the other hand, if $a=S(b)$, then $$S(0)=S(b)+S(b)=S(S(b)+b)=S(b+S(b))=S(S(b+b))$$ where in the middle step I'm using commutativity of addition which I assume we have already proved. But the successor function is required to be injective, so the extremes of this equation gives $0=S(b+b)$ which again contradicts the $S(x)\ne 0$ axiom.

Therefore there is no $a$ such that $1=a+a$ -- in other words, $1$ is not even.

-
Exercise: reorganize this inelegant mess into a direct proof (by induction on $a$) that $a+a\ne 1$ for all $a$. – Henning Makholm Nov 10 '12 at 20:15

Here is another short proof that that $1$ is not even. It does not go down to the foundations like Henning's, but may be appropriate depending on the tools you are working with.

Consider the expression $1 \div 2$. By the Division Algorithm, there are unique $q$ and $r < 2$ such that $$1 = 2q + r,$$ Since $1 < 2$, it must be that $q = 0$ and $r = 1$, that is $$1 = 2\cdot 0 + 1.$$ Since we have a nonzero remainder, it follows that $2$ does not divide $1$. That is, $1$ is not even.

-

If $n$ is even, then

$$n\equiv 0 \quad(\mod2) \quad\text {and} \quad n+1 \equiv 1\quad (\mod2)$$

which implies that $n+1$ is not even.

-

Proving an axiom is comparitively hard. For that, we have to use another axiom which is much more complicated than the hypothesis.

So, I have two proofs.

• Contradiction: Assume that $n$ and $n + 1$ are both even. This implies that for some $p \in \mathbb Z$, $\ \ n = 2p$ and so $n + 1 = 2p + 1$. But all numbers in the form $2 p + 1$ are of the odd parity. Q.E.D.
• Modular arithmetic: We know that if $n \pmod{2} \equiv0$, it follows that $n+1\pmod2 \equiv1$ which implies that $n + 1$ is odd.
-