Am I allowed to change induction hypothesis?

Question

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.

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

Answer 2

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