Proof:Every natural number has a prime factorization
We use strong induction to avoid the notational overhead of strengthening the inductive hypothesis. This proof has the simplicity of the incorrect weak induction proof, but it actually works. You should compare the three versions of the proofs to understand the differences.
Since prime factorizations.Let and must be less than , we can apply and to conclude that both and have 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 .