|
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
is true for all $N$. So: our induction hypothesis is going to be:
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 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. 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. |
|||||||||||||||
|
