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

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!

• You need to prove for $n=(k+2)$ since odd numbers form an AP with first term $a=1$ and common difference $d=2$. Mar 24 '15 at 18:09
• Why would I prove k + 2 when the problem is clearly asking for k + 1? If I had 1, wouldn't k + 2 be 3, which is not even? Mar 24 '15 at 18:11
• you need to prove that "if $x$ is odd, $x+1$ is even." Say the assumed case is $P(k)$ where $P$ is the statement in question. Now, that suggests $k$ is odd. If you try the inductive step with $n=k+1$, you're taking an even value for the inductive step as $k$ is odd. So, $P(k+1)$ can never be true. Mar 24 '15 at 18:14
• Why would someone want to use induction here? Mar 24 '15 at 18:15
• $P(2k)$ is vacuously true. Mar 24 '15 at 18:21

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).

• I'm just learning this and I'm really confused. Do you mind working the problem out step by step with explanations next to each step so that I could learn from it? Mar 24 '15 at 18:15
• I would vastly prefer to see you attempt the steps yourself; if you do this, I will stick with you through the process until it makes sense. I will at least break it into smaller pieces for you - tell me which of them do not make sense. Mar 24 '15 at 18:27
• Props for being patient and so willing to help the OP. +1 Mar 24 '15 at 18:28

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.

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?

• [I'm not the one who downvoted.] Note that if the definition of odd is "not even" (say, $k$ is odd if $\not\exists \ell\in\mathbb{N} : 2\ell = k$) then I don't think you can really get around the induction (possibly in the guise of division-with-remainder).
– aes
Mar 24 '15 at 21:15
• @aes Good point. It seems OP has gone off to never-never land. If s/he returns, there are many good answers/comments to add clarity to the question at hand. Mar 24 '15 at 21:16

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?