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!

  • 2
    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.2012-11-10
  • 1
    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)?2012-11-10
  • 0
    simply say the difference of two integers can not be in the interval $]0,1[$.2012-11-10
  • 0
    @F'Ola: But again, how do you know that?2012-11-10
  • 0
    @HenningMakholm, How are you able to catch such fallacies in logic? I would so wish I caught them on my own :'(2012-11-10
  • 1
    @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.2012-11-10
  • 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
    What a coincidence.2012-11-10
  • 0
    Indeed +1 to you2012-11-10
  • 0
    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.2012-11-10
  • 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.