Proof:Every natural number has a prime factorization (strengthened induction hypothesis)

From CS2800 wiki

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 [math]n [/math] has a prime factorization, we prove that, for any given [math]n [/math], every number [math]2, 3, 4, \dots, n [/math] has a prime factorization. Of course, this means that [math]n [/math] itself has a prime factorization, but by proving even more, we allow our inductive step to go through.

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].
We will prove the claim using weak induction, but with a strengthened induction hypothesis. Let [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(n)} [/math] be the statement "for all [math]k [/math] with [math]2 ≤ k ≤ n [/math], there exists prime numbers [math](a_i) [/math] with [math]k = \prod_i a_i [/math]. We will prove [math]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(2)} [/math] and [math]P(n) [/math] assuming [math]P(n-1) [/math].

In the base case, when [math]n = 2 [/math], we will choose an arbitrary [math]k [/math] between [math]2 [/math] and [math]2 [/math]; we see that [math]k [/math] must be 2. 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]\href{/cs2800/wiki/index.php?title=P(n)&action=edit&redlink=1}{P(n)} [/math], in other words that every [math]k ≤ n [/math] has a prime factorization.

Choose an arbitrary [math]k ≤ n [/math]. Since [math]k [/math] and [math]n [/math] are natural numbers, we see that either [math]k ≤ n-1 [/math] or [math]k = n [/math]. If [math]k ≤ n-1 [/math], then we can apply [math]P(n-1) [/math] to find a prime factorization for [math]k [/math]. Thus, the only remaining case is when [math]k = n [/math].

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 now we do know that! Since [math]a \gt 1 [/math] and [math]n = ab [/math], we see that [math]b \leq n - 1 [/math]; similarly [math]a \leq n - 1 [/math]. Therefore we can apply [math]P(n-1) [/math] to conclude that [math]a [/math] and [math]b [/math] have prime factorizations.

We can therefore finish the proof: Let [math]\href{/cs2800/wiki/index.php/Sequence_notation}{(a_i)} [/math] be the prime factorization of [math]a [/math], and let [math]\href{/cs2800/wiki/index.php/Sequence_notation}{(b_i)} [/math] be the prime factorization of [math]b [/math]. If we let [math](c_i) [/math] be the sequence starting with the [math]\href{/cs2800/wiki/index.php/Sequence_notation}{(a_i)} [/math] and ending with the [math]\href{/cs2800/wiki/index.php/Sequence_notation}{b_i} [/math]s (in other words, [math]c_0, c_1, \dots = a_0,a_1,\dots,a_p,b_0, b_1, \dots, b_q [/math]). Then clearly [math]n = \prod c_i [/math].