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.


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)

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.