6
$\begingroup$

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.

7 Answers 7

9

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!

  • 0
    @AustinMohr. So simple yet so profound! Thanks! I will do this everytime now.2012-11-10
3

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.

  • 0
    @AustinMohr done2012-11-10
2

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.

  • 0
    Exercise: reorganize this inelegant mess into$a$direct proof (by induction on $a$) that $a+a\ne 1$ for all $a$.2012-11-10
1

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.

1

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.

1

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.

0

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.