Prove that every positive integer can be expressed as a product of odd number and power of 2.

Question

This is what I am trying to prove:

Prove that every positive integer $n$ can be expressed as the product of an odd number and a power of $2$, that is, for every $n ≥ 1$ there are $h$ in $Z^+$, $h$ odd and $k$ in $Z$, $k ≥ 0$ such that $n = h· 2^k$. HINT: use strong induction.

This is what I have:

By induction on $n$:

Base Case: If $n=1$, then $h=1$ and $k=0$ and $1=1·2^0=1$ as required.

Inductive Step: Assume that for some $m$ in $Z^+$ the statement is true. Now consider $m+1$. If $m+1$ is odd, then $h=m+1$ and $k=0$, so $m+1=(m+1)k^0=m+1$ as required. If $m+1$ is even, then $m+1=2l$ for some $l$ in $Z^+$. Since $l=h·2^k$, $m+1=2l=2·h·2^k=h·2^{k+1}$. Thus, the statement is true.

I'm not really sure if my proof is completly correct, specifically the induction step. I'm also not sure if I proved everything that needs to be proved. Can someone check if I made any errors and if what I did is complete?

Answer 1

First, let me notice how this result easily follows from fundamental theorem of arithmetic: the number $n$ can be written essentially uniquely as $2^{k}\cdot p_1^{e_1}\cdots p_i^{e_i}$, with the $p_j$ odd primes, and the exponents bigger or equal to zero. However, if you do not have this powerful tool at disposition, you can use strong induction: your proof is not totally wrong, the idea is right, just, by strong induction, you have to assume that all numbers up to $m$ have the required property, and so also $l$, which since $m+1$ is even, is strictly smaller than $m+1$.

Answer 2

You definitely have the right idea. And most of it is correct, and you have covered everything you need to cover.

The biggest flaw is a detail at the start: You're phrasing it as though you're using regular (weak) induction, but it is necessary here to use (and you are indeed actually doing) strong induction.

You say

Assume that for some $m$ in $Z^+$ the statement is true. Now consider $m+1$.

which is weak induction. But then, the assumption that you actually use is

Since $l=h·2^k$

which is not what you've assumed, as $l$ is not $m$. (Here you also ought to specify that $h$ is odd, for clarity, especially since that is the fact on which this whole proof hinges; it must be stated explicitly.)

So if you start your inductive step with

Assume that for some $m$ in $Z^+$ the statement is true for every positive integer less than or equal to $m$. Now consider $m+1$.

and specify that $h$ is odd, then this will be a whole lot more correct.

Answer 3

You were told to try strong induction. Suppose all positive integers $<n$ are so expressible. If $n$ is odd, we're done; if $n$ is even, $n/2<n$ can be written as $h2^j$ with $h$ odd, so $n=h2^{k+1}$.