Strong induction sample

Consider the following theorem.

Theorem 17a (6.4: Exercise 17a): For positive integers a and b and all primes p, if p|ab, then either p|a or p|b.

We shall use Theorem 17a to prove the following theorem.

Theorem 17b (6.4: Exercise 17b): For all positive integers n, for all primes p, if p divides the product of n positive integers, then p divides one of the factors.

Proof: (by induction) For all positive integers n, let P(n) be the statement “for all primes p, if p divides the product of n positive integers, then p divides one of the factors”.

Induction step: (∀ n ∈ Z+) ([(∀ k ∈ Z+)(k < n → P(k)] → P(n)).

Let m ∈ Z+ be arbitrary.

Assume for all positive integers k that k 1. For concreteness, let a = (a_1)(a_2)…(a_{m-1})(a_m) be the product of m factors that p divides. Since a = [(a_1)(a_2)…(a _{m-1})][a_m] and p divides a, by Theorem 17a, either p|[(a _1)(a _2)…(a _{m-1})] or p|a_m.

Subcase 2a: p|a_m

In this case, p divides one of the factors, namely a_m.

Subcase 2b: p|[(a_1)(a_2)…(a_{m-1})]

Apply the induction hypothesis with k=m-1 to see that p divides one of a_1,…,a_{m-1}, so it divides one of the factors of a.

By subcase analysis, in case 2, p divides one of the factors, since it does in both subcases and one of the subcase 2a and subcase 2b must hold.

Thus by case analysis, p divides one of the factors of a, since it does in both cases and one of the case 1 and case 2 must hold.

We assumed p divides the product a of m positive integers, and proved p divides one of the factors, so the implication follows. Since p was an arbitrary prime, true for all such, so P(m) is true.
We assumed for all positive k that k < m implies P(k) and proved P(m), so the implication follows.

Since m ∈ Z+ was arbitrary, true for all such. Thus the induction step is complete.

Therefore, by strong induction, for all n ∈ Z+, P(n) is true, and the theorem follows.