proving that for every integer $x$, if $x$ is odd, then $x + 1$ is even (induction)

Question

So I have to write a proof that "for every integer $x$, if $x$ is odd, then $x + 1$ is even". I understand what I have to do but I always get stuck at the last step which is prove that it's true for $k + 1$. Here's what I wrote down as my reasons as part of the proof:

1. The theorem above is true for the base case (when $n=1$).
2. Now lets assume the theorem is true for $n = k$.
3. Now it's time to prove that the theorem is true for $n = k + 1$.
4. If k is odd, then $(k + 1) + 1$ is even.

Is my rational/jump from $3$ to $4$ correct? I feel like I'm missing a step where I have to factor and algebraically solve the problem but I don't know how to go about that. Can someone please help me? Thanks!

Answer 1

You should try instead assuming the theorem is true for all $n \leq k$. (instead of just $n = k$).

Now, consider $k+1$. If $k+1$ is even, there is nothing to prove. If $k + 1$ is odd, we need to show $k + 2$ is even. Use your induction hypothesis here: in particular, you know that for $n = k-1$, if it is odd (can you show this?) then $n + 1 = k$ is even. What can you now conclude about $k + 2$?

Breaking this down into smaller steps.

• Do you understand what the difference is in the induction hypothesis? (assuming for $n \leq k$ rather than $n = k$?)

• Now we have to prove the theorem for the next larger number, $n = k + 1$. Either it is even or odd. What should we do if it is even?

• If it is odd, we need to show the next bigger number, $n + 1 = k + 2$ is even.

• At this point, what does the induction hypothesis say about $k -1$? (i.e. fill in the blanks: "if $k - 1$ is odd, then ____")

• Is $k - 1$ odd? (otherwise the induction hypothesis doesn't say anything much).

• What does this tell you about $k$? (in particular, is it even/odd?)

• What does this tell you about $k + 2$? (the thing we're trying to prove something about).

Answer 2

Note: This is too long to be just a comment and so I'm posting it as an answer.

I'm surprised no one has yet mentioned that a very elementary number-theoretic proof is easily accessible. Induction is really not necessary here and is a good bit of overkill. If this question is a homework question and you are required to use induction, then your teacher should probably have his/her teaching license revoked ($*$laugh$*$). Proofs like these that require one to use induction, in my experience, lead students to view induction as a somewhat artless/useless proof technique, something that is very clearly not true. However, it is possible that you thought induction was necessary here, but I will outline a proof below for you that will show this is not the case.

Non-inductive proof (much simpler): You are given that $x$ is an odd integer. What does this mean? It means that $x=2\ell+1$ where $\ell$ is an arbitrary integer. Similarly, an even integer $j$ may be represented as $j=2m$ where $m$ is an arbitrary integer. Thus, you have the following: $$ x+1 = (2\ell+1)+1=2\ell+2=2(\ell+1)=2m, $$ where $x=2\ell+1$ is odd and $m=\ell+1$ represents another arbitrary integer. Since $x+1=2m$ where $m$ is an arbitrary integer, you can rest assured that "for every integer $x$, if $x$ is odd, then $x + 1$ is even," thus proving what you set out to prove. Make sense?

Answer 3

Here is a strong start to the problem. $x$ is odd if it can be written as $x=2n+1$ where $n$ is an integer. The case $n=0$ is true since then $x=1$ and $x+1=(2n+1)+1 = 1+1=2$ is even. Suppose the theorem is true for some $n=k$. Then, if $n=k+1$, $x=2n+1=2(k+1)+1$ and $x+1=...$. To finish this you need to get an expression for this $x+1$ and make the case that this is an even number. Do you think you could do this?

Answer 4

Hint $\ $ Prove instead the stronger statement: exactly one of $\,n\!+\!1,n\,$ is even, i.e. one is odd and the other is even, i.e. let $\,\color{#c00}{P(n)}\,$ be $\, \{n\!+\!1,n\}\equiv \{0,1\}\,\pmod 2.\,$ Now the induction step is easy

$$ {\rm mod}\ 2\!:\,\ \color{#0a0}{n\!+\!2\equiv n}\,\Rightarrow\, \{n\!+\!1,\color{#0a0}{n\!+\!2}\}\equiv \{n\!+\!1,\color{#0a0}{n}\}\overset{\color{#c00}{P(n)}}\equiv \{0,1\}\ \Rightarrow\, P(n\!+\!1)$$

Remark $\ $ Note that the above theorem is the case $\,m = 2\,$ of the frequently useful theorem that any sequence of $\,m\,$ consecutive naturals forms a complete system of reps (remainders) for the integers modulo $\,m.\,$ This can be proved inductively exactly as above.