2
$\begingroup$

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!

$\endgroup$
10
  • $\begingroup$ You need to prove for $n=(k+2)$ since odd numbers form an AP with first term $a=1$ and common difference $d=2$. $\endgroup$ Mar 24 '15 at 18:09
  • $\begingroup$ 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? $\endgroup$
    – Richard
    Mar 24 '15 at 18:11
  • $\begingroup$ 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. $\endgroup$ Mar 24 '15 at 18:14
  • 1
    $\begingroup$ Why would someone want to use induction here? $\endgroup$ Mar 24 '15 at 18:15
  • 2
    $\begingroup$ $P(2k)$ is vacuously true. $\endgroup$
    – BaronVT
    Mar 24 '15 at 18:21
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Richard
    Mar 24 '15 at 18:15
  • 2
    $\begingroup$ 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. $\endgroup$
    – BaronVT
    Mar 24 '15 at 18:27
  • 1
    $\begingroup$ Props for being patient and so willing to help the OP. +1 $\endgroup$ Mar 24 '15 at 18:28
1
$\begingroup$

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.

$\endgroup$
0
0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ [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). $\endgroup$
    – aes
    Mar 24 '15 at 21:15
  • $\begingroup$ @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. $\endgroup$ Mar 24 '15 at 21:16
0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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