Welcome to our community

Be a part of something great, join today!

Induction for writing integers

KOO

New member
Oct 19, 2013
19
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
Jan 26, 2012
1,403
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 [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

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
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

Well-known member
MHB Math Helper
Aug 30, 2012
1,123
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
Jan 30, 2012
2,492
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).