Proving every natural number can be expressed as $2^{x} \cdot {y}$

Question

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.

Answer 1

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$?

Answer 2

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$.

Answer 3

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