1

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.

Yanko
  • 13,758
Metaozis
  • 177
  • Your predicate $P(n)$ doesn't make sense if you finish it with "for all such $n$"... – 5xum Sep 19 '18 at 13:37
  • You are definitely going to need strong induction. – Theo Bendit Sep 19 '18 at 13:39
  • Maybe you can simplify the formula replacing it with $n=2^k(2m+1)$. – Mauro ALLEGRANZA Sep 19 '18 at 13:41
  • 1
    @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). – hmakholm left over Monica Sep 19 '18 at 13:41
  • 1
    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. – Mauro ALLEGRANZA Sep 19 '18 at 13:42
  • I have already attempted P(n)=∃k∃m(n=2k(2m+1)), and still stuck when trying to prove P(k+1), I don't know where goes wrong in the process, and I don't understand why strong induction works here since I think assume from P(1) to P(k) won't help me neither... – Metaozis Sep 19 '18 at 13:48
  • @Metaozis If $P(k)$ is true for $k=1,2,\ldots,n$ and $n+1$ is even then $\frac{n+1}{2}$ is an integer and $\frac{n+1}{2} < n$ so $P(\frac{n+1}{2})$ is true. Show that $P(\frac{n+1}{2}) \implies P(n+1)$. – Winther Sep 19 '18 at 16:03

2 Answers2

1

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.

Wuestenfux
  • 20,964
  • 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. – Metaozis Sep 19 '18 at 14:05
  • And then I stuck there, I don't see how algebraic property can lead me to P(k+1). – Metaozis Sep 19 '18 at 14:11
0

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 $ ].

Peter
  • 11
  • 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. – Metaozis Sep 19 '18 at 14:31
  • 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. – Peter Sep 20 '18 at 15:31