CS202: Discrete Structures

3.5 Strong Mathematical Induction

There is a second form of the principle of mathematical induction which is useful in some cases. To apply the first form of induction, we assume P(k) for an arbitrary natural number k and show that P(k + 1) follows from that assumption. In the second form of induction, the assumption is that P(x) holds for all x between 0 and k inclusive, and we show that P(k + 1) follows from this. This gives us a lot more to work with when deducing P(k + 1). We will need this second, stronger form of induction in the next two sections. A proof will be given in the next chapter.

Theorem 3.9. Let P be a one-place predicate whose domain of discourse includes the natural numbers. Suppose that P(0) is true and that

(P(0) ∧ P(1) ∧ · · · ∧P(k)) → P(k + 1)

is true for each natural number k ≥ 0. Then P(n) is true for every natural number n.

For example, we can use this theorem to prove that every integer greater than one can be written as a product of prime numbers (where a number that is itself prime is considered to be a product of one prime number). The proof illustrates an important point about applications of this theorem: When proving P(k + 1), you don't necessarily have to use the assumptions that P(0), P(1), …, and P(k) are true. If P(k + 1) is proved by any means – possibly including the assumptions – then the statement (P(0) ∧ P(1) ∧ · · · ∧ P(k)) → P(k + 1) has been shown to be true. It follows from this observation that several numbers, not just zero, can be 'base cases' in the sense that P(x + 1) can be proved independently of P(0) through P(x). In this sense, 0, 1, and every prime number are base cases in the following theorem.

Theorem 3.10. Every natural number greater than one can be written as a product of prime numbers.

Proof. Let P(n) be the statement "if n > 1, then n can be written as a product of prime numbers". We will prove that P(n) is true for all n by applying the second form of the principle of induction.

Note that P(0) and P(1) are both automatically true, since n = 0 and n = 1 do not satisfy the condition that n > 1, and P(2) is true since 2 is the product of the single prime number 2. Suppose that k is an arbitrary natural number with k > 1, and suppose that P(0), P(1), …, P(k) are already known to be true; we want to show that P(k + 1) is true. In the case where k + 1 is a prime number, then k + 1 is a product of one prime number, so P(k + 1) is true.

Consider the case where k + 1 is not prime. Then, according to the definition of prime number, it is possible to write k + 1 = ab where a and b are numbers in the range from 2 to k inclusive. Since P(0) through P(k) are known to be true, a and b can each be written as a product of prime numbers. Since k + 1 = ab, k + 1 can also be written as a product of prime numbers. We have shown that P(k + 1) follows from P(0) ∧ P(1) ∧ · · · ∧ P(k), and this completes the induction.

3.7.3 Course of Values Induction

A second variation allows for the expansion of the induction hypothesis. The course-of-values principle includes the previous generalization. It is also some- times called strong induction.

Theorem 3.7.9: The Course-of-Values Principle of Mathematical Induction. If p(n) is a proposition over {k₀, k₀ + 1, k₀ + 2, . . .}, where k₀ is any integer, then p(n) is a tautology if

1. p(k₀) is true, and
2. for all n ≥ k₀, p(k₀), p(k₀ + 1), ..., p(n) ⇒ p(n + 1).

A prime number is defined as a positive integer that has exactly two positive divisors, 1 and itself. There are an infinite number of primes. The list of primes starts with 2, 3, 5, 7, 11, . . . . The proposition over {2, 3, 4, ...} that we will prove here is p(n): n can be written as the product of one or more primes. In most texts, the assertion that p(n) is a tautology would appear as

Theorem 3.7.10: Existence of Prime Factorizations. Every positive integer greater than or equal to 2 has a prime decomposition.

Proof. If you were to encounter this theorem outside the context of a discussion of mathematical induction, it might not be obvious that the proof can be done by induction. Recognizing when an induction proof is appropriate is mostly a matter of experience. Now on to the proof!

Basis: Since 2 is a prime, it is already decomposed into primes (one of them).

Induction: Suppose that for some n ≥ 2 all of the integers 2 , 3, ..., n have a prime decomposition. Notice the course-of-value hypothesis. Consider n + 1. Either n + 1 is prime or it isn't. If n + 1 is prime, it is already decomposed into primes. If not, then n + 1 has a divisor, d, other than 1 and n + 1.

Hence, n + 1 = cd where both c and d are between 2 and n. By the induction hypothesis, c and d have prime decompositions, c₁c₂· · · c_s and d₁d₂· · · d_t , respectively. Therefore, n + 1 has the prime decomposition c₁c₂· · · c_sd₁d₂· · · d_t.

Peano Postulates and Induction. Mathematical induction originated in the late nineteenth century. Two mathematicians who were prominent in its development were Richard Dedekind and Giuseppe Peano. Dedekind developed a set of axioms that describe the positive integers. Peano refined these axioms and gave a logical interpretation to them. The axioms are usually called the Peano Postulates.

Axiom 3.7.11: Peano Postulates. The system of positive integers consists of a nonempty set, ℙ; a least element of ℙ, denoted 1; and a "successor function", s, with the properties

1. If k ∈ ℙ, then there is an element of ℙ called the successor of k, denoted s(k).
2. No two elements of ℙ have the same successor.
3. No element of ℙ has 1 as its successor.
4. If S ⊆ ℙ, 1 ∈ S, and k ∈ S ⇒ s(k) ∈ S, then S = ℙ.

Notes:

• You might recognize s(k) as simply being k + 1.
• Axiom 4 is the one that makes mathematical induction possible. In an induction proof, we simply apply that axiom to the truth set of a proposition.

Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.