Prove that every positive integer can be expressed as a product of odd number and power of $2$. In other words, prove that for $n \ge 1$, $!h \in \mathbb{Z^+}$, $h$ odd, and $k \in \mathbb{Z}$, $k \ge 0$ such that $n=h·2^k$.
I did the base case: If $n=1, h=1, k=0$, then $n=h\times 2^k$ is $1=1\times2^0=1$. But I am having a hard time with the induction step. How do you finish the proof?
On
represent that number in binary.it is well known that every number has exactly one unique binary representation.if given number(suppose N) has 1 at the start of the binary representation than it is $2^0*N$, N is odd because binary representation starts with 1, example 5=101, 7=111, 9=01001,they all start with 1.if it doesn't start with 1,than count the number of 0 s before we meet 1, so 6=110, we have 1 zero before 1 st one, 8=1000, we have 3 zero's before 1, so count zeroes than rise 2, in that power and multiply that number by remaining number, so 6=110, we take 2 in 1(1 zero before 1st one), power and multiply it by 3(11, remaining), it is easy to show that it gives the unique representation of product of odd and number that is power of 2.
HINT
One approach is to use 2 base cases, $n=1$ and $n=2$. Then, consider even and odd numbers separately, applying the inductive hypothesis to $n-2$ in each case.
May be simpler to avoid induction altogether. If you have an even number, factor out the largest integer power of 2 possible. Otherwise let $k=0$ and you are done.