# Proving that every natural number can be written as a product of odd integer and a a non-negative integer power of 2.

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)

• What if you divide $k+1$ by $2$ if it's even? – saulspatz Mar 10 at 23:21
• Will we get $\frac{k+1}{2} < k+1$, based on our Induction Hypothesis? – Harry Battersby Mar 10 at 23:24
• Of course $\frac{k+1}{2}<k+1$. Therefore, the induction hypothesis applies to $\frac{k+1}{2}$ – saulspatz Mar 10 at 23:24
• Do we know this is true since $n \in \mathbb{N}$? Or is it because we are relying on the Inductive Hypothesis here? – Harry Battersby Mar 10 at 23:25
• Yes, that's right. – saulspatz Mar 10 at 23:27

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