# Proof:Every natural number has a prime factorization (weak induction; doesn't work)

We will attempt to use weak induction to prove the following claim:

For all , if then there exists prime numbers with .
Proof: Attempt with weak induction
We will prove the claim using weak induction. Let be the statement "there exists prime numbers with . We will prove and assuming .

In the base case, when we see that 2 is prime. Therefore, we can choose ; clearly .

For the inductive step, we assume ; our goal is to show , in other words that has a prime factorization.

There are two cases: could be prime or composite. If is prime, we can proceed as in the base case: simply choose .

If, on the other hand, is composite, then we know that for some natural numbers and .

If we knew that and had prime factorizations, then we could combine them to form a prime factorization of . But we don't know that — it is what we are trying to prove. We do have an inductive hypothesis that tells us that has a prime factorization, but that only helps if .

To fix this up, we need to either strengthen our inductive hypothesis or use strong induction.