Proving every natural number can be expressed as $2^{x} \cdot {y}$ I need help proving every natural number can be expressed as $2^{x} \cdot {y}$, where $x$ is a non-negative integer, and $y$ is an odd positive integer.
I thought that maybe using Strong Induction was a good idea, but I can't figure out what the base case should be. I have never done induction with two variables before.
Also when $n$ is odd, we can just write $n^{0}\cdot y$, where $n = y$, but the even case is tricky.
 A: Doing it by strong induction is a good idea.
Hint: the case $n=1$ is trivial. Now, take $n\in\mathbb N$ and suppose that the statement is true for every $k\in\{1,2,\ldots,n\}$. Does it hold for $n+1$. If $n+1$ is odd, it's trivial. (Why?) And if $n+1$ is even, what can you tell us about $\frac{n+1}2$?
A: Here is an equivalent statement:
The function: 
$$f:\mathbb{Z}_{\ge 0} \times \left\{2y+1:y \in \mathbb{Z}_{\ge 0}\right\} \to \mathbb{Z}_{>0}$$ 
given by:
$$f(x,y) = 2^xy$$
is a bijection.
Proof that it is an injection:
$$f(x_1,y_1) = f(x_2,y_2)$$
$$2^{x_1}y_1 = 2^{x_2}y_2$$
We must have $2^{x_1}|2^{x_2}y_2$. Since $y_2$ is odd, we must have $2^{x_1}|2^{x_2}$, so $x_2\ge x_1$.
Similarly, we must have $2^{x_2}|2^{x_1}y_1$, and by the same argument, $x_1\ge x_2$, so $x_1=x_2$.
Then, we cancel and that shows that $y_1=y_2$.
Proof that it is a surjection:
Let $n \in \mathbb{Z}_{>0}$. Let $x$ be the largest power of 2 that divides $n$. We know this exists by the prime factorization theorem, and we know it is a nonnegative number. Then $\dfrac{n}{2^x}\in \mathbb{Z}$, and since there does not exist a larger power of 2 that divides $n$, it must be that 2 does not divide $\dfrac{n}{2^x}$. So, let $y=\dfrac{n}{2^x}$. Now, $f(x,y)=n$.
A: You have already seen that for $x=0$, $2^x\cdot y=y$; so every odd number can be represented in the desired form.
Now just think about what an even natural number is. It is a number containing one or more factors of $2$. If you abstract all of the factors of two from an even number (and let us say there are $x\ge 1$ of them) what remains is an odd number (let's call it $y$). If the natural number being looked at was a perfect power of $2$, then $y=1$. Otherwise, $y$ is some other odd number. Either way, the original even number has the form $2^x\cdot y$. QED
