Construction of Natural Numbers

Question

I am trying to prove that the natural numbers can be constructed from the product of a power of $2$ and an odd number.

For all $n \neq 0$ in the natural numbers, $n = (2k+1)(2^p)$, where $k$ and $p$ are natural numbers, inclusive of zero.

I've started a proof by induction.

For the base case, I have one for odd and another for the even base case.

So, for odd, I set $n = 1, k = 0, p = 0$.

Then $n = (2(0) + 1)(2^0) = 1$

For even, I set $n = 2, k = 0, p = 1$

Then $n = (2(0) + 1)(2^1) = 2$

Then, for the inductive step, I have that, whenever $n$ is not divisible by $2$, then $p = 0$. So $n = 2k + 1 \equiv 1 \pmod 2$ and $n + 2 = (2(k+1) + 1)(2^0) = (2k+3) \equiv 1 \pmod 2$. Thus, it proves every successive odd number.

Then, whenever $n$ is divisible by $2$, then $p$ is a natural number $> 0$. So, $n = (2k + 1)(2^p) \equiv 0 \pmod 2$ and $n + 2 = (2(k+1) + 1)(2^p) = (2k + 3)(2^p) \equiv 0 \pmod 2$

I'm just wondering if this is the proper way to approach my inductive step for the even and odd.

Answer 1

Well for even numbers. You will set $p=0$ and you basically keep incrementing the $k$ by 1 in C++ notation its $k++$ and in mathematics notation it's $k+1$ and so Given that $2k+1$ is odd , it's very obvious that $2(k+1)+1 = 2k+3$ is odd and on the other hand for odd numbers , you set $k=0$ and then you increment your $p$ and it's also obvious that if $2^p$ is even that $2^{p+1} = 2(2^p)$ which is even. U should also mention that $p \geq 1 $ when you construct the even numbers

Answer 2

The proof can be organized with strong induction, which is equivalent to normal induction but sometimes gives a clearer proof.

First, the base case $n=1$ is $1\cdot 2^0$, a product of an odd number and a power of two.

Second, let $n>1$ and assume that the statement holds for all $1\leq m<n$. If $n$ is odd, then $n=n\cdot 2^0$. If $n$ is even, say $n=2k$, then since $1\leq k<n$ we have by the induction hypothesis $k=c\cdot 2^\ell$ for some odd $c$ with some $\ell\geq 0$, and so $n=2\cdot c\cdot 2^\ell=c\cdot 2^{\ell+1}$.

This completes the proof.

In your proof, the odd case is correct, but I notice a mistake in the even case: it is not true that $(2k+1)2^p+2=(2k+3)2^p$ when $p>0$.