The prime factorization including both existence and uniqueness. I have totally no idea about this problem except the basecase.
In this problem we only consider number greater or equal to 2. So the basecase should be n=2, and it is easy to prove. But for I.H, I have no idea, should I make I.H be n = ${p_1p_2...p_i}$ or sort of things? Is there any hints for me?
Thank you.
I'll show the existence part, which is where the induction is used. For this proof, it is easiest to use strong induction: you don't simply assume the case $n-1$ in order to prove $n$, but you assume all cases less than $n$. Using this, the proof is rather simple:
The case $n=2$ is our base case, which is obvious. Now let $n$ be any natural number greater than $2$, and assume for our induction hypothesis that a prime factorization exists for every $1<m<n$. If $n$ is prime, then we're done. Otherwise, $n=ab$ where $a,b>1$. Use our induction hypothesis to complete the proof.