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:

Claim (see proof):

For all [math]n \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math], if [math]n ≥ 2 [/math] then there exists prime numbers [math]a_0, a_1, \dots, a_k [/math] with [math]n = a_1 \cdot a_2 \cdots a_k [/math].

Proof: Attempt with weak induction

We will prove the claim using weak induction. Let [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(n)} [/math] be the statement "there exists prime numbers [math]a_0, a_1, \dots, a_k [/math] with [math]n = a_1 \cdot a_2 \cdots a_k [/math]. We will prove [math]P(2) [/math] and [math]P(n) [/math] assuming [math]P(n-1) [/math].

In the base case, when [math]n = 2 [/math] we see that 2 is prime. Therefore, we can choose [math]a_0 = 2 [/math]; clearly [math]2 = 2 [/math].

For the inductive step, we assume [math]P(n-1) [/math]; our goal is to show [math]P(n) [/math], in other words that [math]n [/math] has a prime factorization.

There are two cases: [math]n [/math] could be prime or composite. If [math]n [/math] is prime, we can proceed as in the base case: simply choose [math]a_0 = n [/math].

If, on the other hand, [math]n [/math] is composite, then we know that [math]n = ab [/math] for some natural numbers [math]a [/math] and [math]b [/math].

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

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