Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 10 down vote accepted

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.

share|improve this answer
    
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

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.

share|improve this answer
2  
@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
1  
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

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.