Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

7 Answers

up vote 9 down vote accepted

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!

share|improve this answer
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. –  Austin Mohr Nov 10 '12 at 19:48
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)? –  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
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. –  Austin Mohr Nov 10 '12 at 22:04
show 2 more comments

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.