Construction of Natural Numbers 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.
 A: 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
A: 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$.
