Am I allowed to change induction hypothesis? 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.


*

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

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

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

*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. 
 A: 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.
A: 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 $ ]. 
