I am doing the exercise from my textbook teaching the induction and stuck for a long time about the induction hypothesis part.

The question is the following:

Let $n \in \mathbb N \backslash \{0\}$, use some form of induction to prove that for all such n there exists an odd natural $m$ and a natural $k$ such that $n = 2^{k}m$.

From my lecture my prof told us that we have to use $P(n)$ to prove $P(k+1)$ and can't use $P(k+1)$ as a precedent, I understand this part, and the following is my approach.

  1. Define predicate $P(n) =$ there exists an odd natural $m$ and a natural $k$ such that $n = 2^{k}m$ for all such $n$.

  2. Check $P(1)$, if I choose $k = 0$ and $m = 1$ this holds.

  3. Assume $P(h)$ is True, namely, I can find such $m$ and $k$ so that $h = 2^{k}m$.

  4. Prove $p(h+1)$, I know I have to show two cases since $P(h+1)$, so I assume $P(h) + 1$ is odd first, then I can write $h+1 = 2^{k}m + 1$, and get $h = 2^{k}m$, and by I.H. this is true. (Although I don't think I get this correctly it just looks weird). Then I assume $h+1$ is even, this implies that h must be odd, so induction hypothesis must be changed to $h = 2^{k}m + 1$ in this case, so $h+1 = 2^{k}m + 2$, then get $h + 2^{k}m + 1$, by I.H this is true.

I don't know what goes wrong in my proof, but when I just stare at it I just feel it is not correct, I need help to explain this question, thanks.

  • $\begingroup$ Your predicate $P(n)$ doesn't make sense if you finish it with "for all such $n$"... $\endgroup$ – 5xum Sep 19 '18 at 13:37
  • $\begingroup$ You are definitely going to need strong induction. $\endgroup$ – Theo Bendit Sep 19 '18 at 13:39
  • $\begingroup$ Maybe you can simplify the formula replacing it with $n=2^k(2m+1)$. $\endgroup$ – Mauro ALLEGRANZA Sep 19 '18 at 13:41
  • 1
    $\begingroup$ @TheoBendit: It looks like he's effectlvely reinventing the proof that strong induction works, by changing the induction predicate from $p(n)$ to $\forall k\le n: p(k)$. (There are a number of notational hiccups in the question that somewhat obscure this, though). $\endgroup$ – hmakholm left over Monica Sep 19 '18 at 13:41
  • 1
    $\begingroup$ If so, we have $P(n)= \exists k \exists m (n=2^k(2m+1))$. For $n=1$ we have that $k=m=0$ will do. $\endgroup$ – Mauro ALLEGRANZA Sep 19 '18 at 13:42

Let $P(n)$ be the predicate in $n\in{\Bbb N}_0$ to be proved.

Induction base: show that $P(0)$ holds.

Induction step: suppose $P(0)\wedge\ldots \wedge P(n)$ holds. Then prove $P(n+1)$, i.e., $\forall n\in{\Bbb N}_0: [P(0)\wedge\ldots \wedge P(n) \rightarrow P(n+1)]$.

The mathematics or logic behind is the following:

$P(0)$ is true by the induction base.

$P(0)\Rightarrow P(1)$ holds by the induction step. By the rule of modus ponens (i.e., if $A$ is true and $A\Rightarrow B$ is true, then $B$ is true), it follows that $P(1)$ is true.

$P(0)\wedge P(1)\Rightarrow P(2)$ holds by the induction step. Since $P(0)\wedge P(1)$ is true, so by modus ponens $P(2)$ is true.

And so on. So you have proved $\forall n\in{\Bbb N}_0: P(n)$.

Often one requires only $P(n)$ to prove $P(n+1)$, i.e., the induction step is $\forall n\in{\Bbb N}_0: [P(n) \rightarrow P(n+1)]$. The mathematics behind is the same.

  • $\begingroup$ Thanks for replying, I actually have a little clue about the frame of complete proofs, but I think I just haven't practiced enough to see how and why this pattern fits the question I posted above. My understanding of this is that if I have to prove P(k+1) by using P(k) to start, then the above question can always be divided into P(k+1) = P(k) + P(1), which is not same as P(k) ∧ P(1) I guess. $\endgroup$ – Metaozis Sep 19 '18 at 14:05
  • $\begingroup$ And then I stuck there, I don't see how algebraic property can lead me to P(k+1). $\endgroup$ – Metaozis Sep 19 '18 at 14:11

Assuming that $n$ and $i$ are natural numbers, and that you have proved $p(0)$.

Normal induction - prove that if $p(n)$ then $p(n+1)$.

Strong induction - prove that if $p(i)$ for all $ i \le n $ then $p(n+1) $.

(This would imply that $p(i) $ for all $ i \le n+1$).

You are allowed to do this - let $P(n)$ be [ $ p(i)$ for all $i \le n $ ].

  • $\begingroup$ Thanks for replying, I know how strong induction frame goes, but I don't see why it applies to the question above at this time since there is no pattern from m to k before P(k+1), I don't see what algebra properties it can brings to me to solve the above question. $\endgroup$ – Metaozis Sep 19 '18 at 14:31
  • $\begingroup$ Assuming P(h) - the strong induction version. If h is even, h+1 is odd, and you can do it. If h is odd, h+1 is even, so h+1 = 2g (say) and g satisfies the hypothesis so you can prove h+1 does. Hope this helps. $\endgroup$ – Peter Sep 20 '18 at 15:31

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.