Induction for writing integers

[KOO]

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 = 2² * 9

 

[Prove It]

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 = 2² * 9

If n is odd, we can write it as [tex]\displaystyle \begin{align*} n = n \cdot 2^0 \end{align*}[/tex].

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

Q.E.D.

 

[Evgeny.Makarov]

If n is odd, we can write it as [tex]\displaystyle \begin{align*} n = n \cdot 2^0 \end{align*}[/tex].

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

This is not enough to prove the required claim.

 

[topsquark]

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 = 2² * 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]

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