Prove that all positive integer has a unique representation of the form $2^a.b$ , where $a$ is a non-negative, $b$ is odd.

Question

In this link Prove that every positive integer $n$ has a unique expression of the form: $2^{r}m$ where $r\ge 0$ and $m$ is an odd positive integer we have a proof without induction (and I understand it). But my teacher wants us to use induction to solve this problem.

How do I go from this: $n = 2^a.b$, to this: $n + 1 = 2^a.b + 1 = 2^c.d$ for some $c$ and $d$?

Answer 1

It is better if the induction is a different one, I mean, suppose that for any number less than $n$, the property holds, then show that the property also holds for $n$. In this case, you can divide it into two cases. First, if $n$ is odd, you are done. Secondly, if $n$ is even. So $n=2k$ for some $k<n$, now apply the property to $k$, which says that $k=2^am$, where $m$ is an odd number, and then $n=2^{a+1}m$ and you get what you want. I hope this proof provides a tool for settling this question using induction.

Answer 2

You can prove by induction. When $n$ is odd, you are done. When $n$ is even, you factor a 2 out, and represent $n/2$ by induction.