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