Proof by Strong Induction: $n = 2^a b,\, b\,$ odd, every natural a product of an odd and a power of 2 Can someone guide me in the right direction on this question?

Prove that every $n$ in $\mathbb{N}$ can be written as a product of an odd integer and a non-negative integer power of $2$.

For instance: $36 = 2^2(9)$ , $80 = 2^4(5)$ , $17 = 2^0(17)$ , $64 = 2^6(1)$ , etc...

Any hints in the right direction is appreciated (please explain for a beginner).
Thanks.
To prove something by strong induction, you have to prove that


  If all natural numbers strictly less than $N$ have the property, then $N$ has the property.


is true for all $N$. 

So: our induction hypothesis is going to be:


  Every natural number $k$ that is strictly less than $n$ can be written as a product of a power of $2$ and an odd number.


And we want to prove that from this hypothesis, we can conclude that $n$ itself can be written as the product of a power of $2$ and an odd number.

Well, we have two cases: either $n$ is odd, or $n$ is even. If we can prove the result holds in both cases, we'll be done.

Case 1: $n$ is odd. Then we can write $n=2^0\times n$, and we are done. So in Case 1, the result holds for $n$.

Case 2: If $n$ is even, then we can write $n=2k$ for some natural number $k$. But then $k\lt n$, so we can apply the induction hypothesis to $k$. We conclude that ...and you should finish this part...

So we conclude that the result holds for all natural numbers by strong induction.
Proof:

By the fundamental theorem of algebra, every integer $N$ can be uniquely factored as $\prod^{n}_{i=1}p_{i}^{a_{i}}$. Now, mark $2=p_{1}$, note $a_{i}$ can take value of $0$. You got the theorem. 

For the "inductive" proof, suppose for $n&lt;k$ this is true. For $n+1$ its factors must be in previous $n$ numbers. Hence $n+1=\prod n_{i}$. Decompose $n_{i}$ by induction hypothesis you get the statement.