Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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, which shows that for multiplicative sets we need only check the generators (here $1$ and primes).
Lemma $\rm\, \mathbb N$ is the only set of naturals containing $\color{#c00}1$ and $\rm\color{#c00}{all\ primes}$ and $\rm\color{#0a0}{closed\ under\ multiplication}$
Proof $\ $ Suppose $\rm\!\ N\subset \mathbb N\:$ has said properties. $ $ We prove by strong induction every natural $\rm\!\ n\in N.\, $ If $\rm\:n\:$ is $\,\color{#c00}1\,$ or $\color{#c00}{\rm prime}$ then by hypothesis $\rm\:n\in N.\:$ Else $\rm\,n\,$ is composite, $ $ hence $\rm\ n = j k\ $ for $\rm\: j,k < n.\:$ By strong induction the smaller $\rm\ j,k\in N,\:$ $\rm\color{#0a0}{thus}$ $\rm\: n = jk\in N.\ \ \ $ QED
This yields the sought result. Let $\rm\!\ N\!\ $ be the set of naturals that have the form $\rm\,2^{\,j}\!\ n\:$ for odd $\rm\:n\in \mathbb N.\ $ $\, 1\!\ $ and all primes $\rm\,p\,$ are in $\rm\!\ N,\, $ by $\, 2 = 2^{\!\ 1}\!\cdot\! 1\,$ and $\rm\, p = 2^{\!\ 0}\!\cdot\! p\,$ for odd $\rm\,p\,$ (and $1).$ $\rm\,N\!\ $ is closed under multiplication by $\rm\, (2^{\,j}\!\ m)\ (2^{\,k}\!\ n) = 2^{\,j+k}\!\ m\!\ n,\: $ with $\rm\!\ m\!\ n\!\ $ odd by $\rm\!\ m,n\!\ $ odd. $\!\ $ So $\rm\ N = \mathbb N\ $ by Lemma.
Corollary $\ $ Every natural $> 0\,$ is a product of primes (i.e. irreducibles).
Proof $\, $ It is clear for $1$ and primes, and products of primes are closed under multiplication.
Remark $ $ One could deduce the sought result from the prior Corollary. Then it reduces to (inductively) proving that a product of $n$ odds remains odd. But this way is not an instructive example of strong induction, since the strong induction is hidden in the proof of the corollary.
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.
