Proof:Every natural number has a prime factorization (strengthened induction hypothesis)
Here is a corrected version of the proof that Every natural number has a prime factorization wherein we strengthen the inductive hypothesis. You may find it useful to read them side by side to understand the differences.
There is a lot of technicality involved in this proof that doesn't really help explain what's going on; it is much clearer to write essentially the same proof using strong induction. This is an example to demonstrate that you can always rewrite a strong induction proof using weak induction.
The key idea is that, instead of proving that every number prime factorization, we prove that, for any given , every number has a prime factorization. Of course, this means that itself has a prime factorization, but by proving even more, we allow our inductive step to go through.has a
If we knew that prime factorizations, then we could combine them to form a prime factorization of . But now we do know that! Since and , we see that ; similarly . Therefore we can apply to conclude that and have prime factorizations.We can therefore finish the proof: Let and had be the prime factorization of , and let be the prime factorization of . If we let be the sequence starting with the and ending with the s (in other words, ). Then clearly .