# Induction for writing integers

#### KOO

##### New member
Prove that every n E N can be written as a product of odd integer and a non-negative integer power of 2.

For instance: 36 = 22 * 9

#### Prove It

##### Well-known member
MHB Math Helper
Prove that every n E N can be written as a product of odd integer and a non-negative integer power of 2.

For instance: 36 = 22 * 9
If n is odd, we can write it as \displaystyle \begin{align*} n = n \cdot 2^0 \end{align*}.

If n is even (including 0), it must have a factor of 2, so we can write it as \displaystyle \begin{align*} n = 2^1 k \end{align*}.

Q.E.D.

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
If n is odd, we can write it as \displaystyle \begin{align*} n = n \cdot 2^0 \end{align*}.

If n is even (including 0), it must have a factor of 2, so we can write it as \displaystyle \begin{align*} n = 2^1 k \end{align*}.
This is not enough to prove the required claim.

#### topsquark

##### Well-known member
MHB Math Helper
Prove that every n E N can be written as a product of odd integer and a non-negative integer power of 2.

For instance: 36 = 22 * 9
What about powers of 2? 2^k (k being a positive integer) has no odd factors, unless you want to include 1.

-Dan

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
What about powers of 2? 2^k (k being a positive integer) has no odd factors, unless you want to include 1.
Well, we want to include 1. Thus, if $k$ is a nonnegative integer, then $2^k=1\cdot2^k$: here 1 is an odd integer and $2^k$ is a non-negative integer power of 2, so this factorization satisfies the problem statement.

Obviously, a proof of this fact uses repeated division by 2. It can be made precise using strong induction.

There was another thread here about MathStackExchange (MSE), and the format that encourages dialogue was mentioned as a feature that distinguishes this forum from MSE. So I suggest that the OP write his/her reaction to what has been said so far and also the topic that this problem is supposed to teach (such as strong induction, direct proofs, or divisibility).