The question is as follows:
Prove that every $n \in \mathbb{N}$ can be written as a product of an odd integer and a nonnegative integer power of $2$.
For instance, $36 = 9 \cdot 2^2, 80 = 5 \cdot 2^4, 17 = 17 \cdot 2^0, \text{etc...}$
Hint: Use strong induction on $n$. In the induction step, treat the cases 'k even' and 'k odd' seperately.
Unfortunately, I don't really know how to finish this proof, and I'm not completely sure if the structure and information that I specified in it are even correct.
That is what I have done so far.
Proof
Let $P(n)$ be the statement $n=2^ab$, where $n \in \mathbb{N}$, $a\in \mathbb{Z}^+$ and $b$ the set of all odd integers.
Base Case:
Let $n=1$, then we get $1 = 2^0 \cdot 1$. Thus, the base case is true.
Induction Hypothesis:
Suppose $P(1), P(2), \cdots,P(k)$ is true for some $k \in \mathbb{N}$ so that we know that every natural number $k < n$ can be written as $k = 2^ab$
Induction Step:
Here, we want to show that $k+1= 2^ab$ to show prove this claim.
Case 1: If $k+1$ is odd, then $k+1 = 2^0(k+1) = k+1$, hence this case is done.
Case 2: If $k+1$ is even, then... (NOT SURE WHAT TO DO HERE)
If $k+1$ is odd, we're done, as you say, so we may suppose that $k+1$ is even. Then $\frac{k+1}2$ is a positive integer $<k+1$, so by the induction hypothesis, there exist positive integers $a,b$, with $b$ odd, such that $$\frac{k+1}2=2^ab.$$ Then $k+1=2^{a+1}b$, so the theorem is true for $k+1$.