# Proof by Strong Induction: every natural a product of an odd and a power of 2

Can someone guide me in the right direction on this question?

Prove that every $n$ in $\mathbb{N}$ can be written as a product of an odd integer and a non-negative integer power of $2$.

For instance: $36 = 2^2(9)$ , $80 = 2^4(5)$ , $17 = 2^0(17)$ , $64 = 2^6(1)$ , etc...

Any hints in the right direction is appreciated (please explain for a beginner). Thanks.

-

To prove something by strong induction, you have to prove that

If all natural numbers strictly less than $N$ have the property, then $N$ has the property.

is true for all $N$.

So: our induction hypothesis is going to be:

Every natural number $k$ that is strictly less than $n$ can be written as a product of a power of $2$ and an odd number.

And we want to prove that from this hypothesis, we can conclude that $n$ itself can be written as the product of a power of $2$ and an odd number.

Well, we have two cases: either $n$ is odd, or $n$ is even. If we can prove the result holds in both cases, we'll be done.

Case 1: $n$ is odd. Then we can write $n=2^0\times n$, and we are done. So in Case 1, the result holds for $n$.

Case 2: If $n$ is even, then we can write $n=2k$ for some natural number $k$. But then $k\lt n$, so we can apply the induction hypothesis to $k$. We conclude that ...and you should finish this part...

So we conclude that the result holds for all natural numbers by strong induction.

-
So if k < n then by induction hypothesis k can be written as a product of a power of 2 and an odd number? Then that would imply that n itself follows from the hypothesis? – 1337holiday Mar 9 '11 at 5:52
@1337holiday: I assume you are talking about case 2. Not "if", but since $k\lt n$, then $k$ can be written as a product of a power of $2$ and an odd number (by the induction hypothesis). So $k=2^r\times s$, where $s$ is odd. What does that tell you about $n$? – Arturo Magidin Mar 9 '11 at 5:53
So since n = 2k and k = (2^r(s)). It means that n = 2(2^r(s)) or n = (2^(r+1))(s) and therefore it is true by the hypothesis? – 1337holiday Mar 9 '11 at 6:00
@1337holiday: Essentially yes: though I would phrase it as "and therefore, $n$ can be written as the product of a power of $2$ and an odd number." The induction hypothesis has already been invoked, no need to remember her yet again in the coda. (-: – Arturo Magidin Mar 9 '11 at 6:02
THIS IS AMAZING! I didnt understand this at all but now im starting to get it. Thanks so much! – 1337holiday Mar 9 '11 at 6:06

This may be deduced from a more general result that's both simpler to prove and more insightful, viz. the result follows immediately by this frequently applicable multiplicative form of induction.

Lemma $\rm\ \mathbb N$ is the only set of naturals containing $1$ and all primes and closed under multiplication.

Proof $\$ Suppose $\rm\!\ N\subset \mathbb N\:$ has said properties. We prove by strong induction that all naturals $\rm\!\ n\in N.$ If $\rm\:n\:$ is $1$ or prime then by hypothesis $\rm\:n\in N.\:$ Else $\rm\:n\:$ is composite hence $\rm\ n\, =\, j\ k\$ for $\rm\: j,k < n.\:$ By induction $\rm\ j,k\in N,\:$ so $\rm\: n\, =\, j\ k\in N,\:$ since $\rm\:N\:$ is closed under multiplication. $\$ QED

This yields the sought result. Let $\rm\!\ N\!\$ be the set of naturals that have the form $\rm\,2^{\,i}\!\ n\:$ for odd $\rm\:n\in \mathbb N.\$ Notice $\!\, 1\!\$ and all primes $\rm\,p\,$ are in $\rm\!\ N,\,$ by $\rm\: 1 =2^{\!\ 0}\!\cdot\! 1 ,\ 2 = 2^{\!\ 1}\!\cdot\! 1,\,$ odd $\rm\, p = 2^{\!\ 0}\!\cdot\! p.\:$ $\rm\!\ N\!\$ is closed under multiplication by $\rm\ (2^{\,i}\!\ m)\ (2^{\,j}\!\ n)\, =\, 2^{\,i+j}\!\ m\!\ n,\:$ with $\rm\!\ m\!\ n\!\$ odd by $\rm\!\ m,n\!\$ odd. $\!\$ So $\rm\ N = \mathbb N\$ by Lemma.

-

Proof:

By the fundamental theorem of algebra, every integer $N$ can be uniquely factored as $\prod^{n}_{i=1}p_{i}^{a_{i}}$. Now, mark $2=p_{1}$, note $a_{i}$ can take value of $0$. You got the theorem.

For the "inductive" proof, suppose for $n<k$ this is true. For $n+1$ its factors must be in previous $n$ numbers. Hence $n+1=\prod n_{i}$. Decompose $n_{i}$ by induction hypothesis you get the statement.

-
@user7887: The Fundamental Theorem of Algebra says that every nonconstant polynomial with complex coefficients has at least one complex root; you mean the Fundamental Theorem of Arithmetic. – Arturo Magidin Mar 9 '11 at 5:37
now I understand. – Kerry Mar 9 '11 at 5:49
@user7887: Your inductive proof has two problems: first, the OP asked for a proof by strong induction, not regular induction. Second, your argument is incorrect as given (it's possible for $n+1$ to be prime, after all). – Arturo Magidin Mar 9 '11 at 5:50
I don't think $n+1=\prod n_i$ is true (should be $p_i$), and if $n+1$ is prime its factor(s) are not in the previous $n$ numbers. You are close-if $n+1$ is prime, it is odd. – Ross Millikan Mar 9 '11 at 5:52
I guess answering more such questions can help me realize my own weakness. Thanks for the comments. – Kerry Mar 9 '11 at 5:54