Skip to main content

Section 6.3 The Second Principle of Mathematical Induction

Let \(P(n)\) be

\(n\) is a prime number or \(n\) is a product of prime numbers.

Suppose we would like to use induction to prove that \(P (n)\) is true for all natural numbers greater than 1. We have seen that the idea of the inductive step in a proof by induction is to prove that if one statement in an infinite list of statements is true, then the next statement must also be true. The problem here is that when we factor a composite number, we do not get to the previous case. For example, if assume that \(P (39)\) is true and we want to prove that \(P (40)\) is true, we could factor 40 as \(40 = 2 \cdot 20\text{.}\) So the assumption that \(P (39)\) is true does not help us prove that \(P (40)\) is true. What we would like to do is use \(P (2)\) and \(P (20)\text{.}\)

This work is intended to show the need for another principle of induction. In the inductive step of a proof by induction, we assume one statement is true and prove the next one is true. The idea of this new principle is to assume that all of the previous statements are true and use this assumption to prove the next statement is true. This is stated formally in terms of subsets of natural numbers in the Second Principle of Mathematical Induction.

The Second Principle of Mathematical Induction.

Let \(M\) be an integer. If \(T\) is a subset of \(\Z\) such that

  1. \(M \in T\text{,}\) and

  2. For every \(k \in \Z\) with \(k \geq M\text{,}\) if \(\{ M, M + 1, \ldots, k \} \subseteq T\text{,}\) then \((k + 1) \in T\text{,}\)

then \(T\) contains all integers greater than or equal to \(M\text{.}\) That is, \(\{ n \in \Z | n \geq M \} \subseteq T\text{.}\)

The primary use of mathematical induction is to prove statements of the form

\begin{equation*} ( \forall n \in \Z, \text{ with } n \geq M)(P(n))\text{,} \end{equation*}

where \(M\) is an integer and \(P (n)\) is some predicate. (For most proofs, \(M = 0\) or \(M = 1\text{.}\) So our goal is to prove that the truth set \(T\) of the predicate \(P (n)\) contains all integers greater than or equal to \(M\text{.}\) To use the Second Principle of Mathematical Induction, we must

  1. Prove that \(M \in T\text{.}\) That is, prove that \(P (M)\) is true.

  2. Prove that for every \(k \in \N\text{,}\) if \(k \geq M\) and \(\{M, M + 1, \ldots, k \} \subseteq T\text{,}\) then \((k + 1) \in T\text{.}\) That is, prove that if \(P(M), P(M + 1), \ldots, P(k)\) are true, then \(P(k + 1)\) is true.

As before, the first step is called the basis step or the initial step, and the second step is called the inductive step. This means that a proof using the Second Principle of Mathematical Induction will have the following form:

Using the Second Principle of Mathematical Induction.

Let \(M\) be an integer. To prove: \(( \forall n \in \Z, \text{ with } n \geq M)(P(n))\)

Basis step

Prove \(P(M)\text{.}\)

Inductive step

Let \(k \in \Z\) with \(k \geq M\text{.}\) Prove that if \(P(M), P(M + 1), \ldots, P(k)\) are true, then \(P(k + 1)\) is true.

We can then conclude that \(P (n)\) is true for all \(n \in Z\) with \(n \geq M\text{.}\)

We will use this procedure to prove the proposition to prove the following proposition.

Proof.

We will use the Second Principle of Mathematical Induction. We let \(P(n)\) be

\(n\) is either a prime number or \(n\) is a product of prime numbers.
For the basis step, \(P(2)\) is true since 2 is a prime number.

To prove the inductive step, we let \(k\) be a natural number with \(k \geq 2\text{.}\) We assume that \(P (2), P(3), \ldots, P(k)\) are true. That is, we assume that each of the natural numbers \(2, 3, \ldots, k\) is a prime number or a product of prime numbers. The goal is to prove that \(P (k + 1)\) is true or that \((k + 1)\) is a prime number or a product of prime numbers.

Case 1

If \((k + 1)\) is a prime number, then \(P(k + 1)\) is true.

Case 2

If \((k + 1)\) is not a prime number, then \((k + 1)\) can be factored into a product of natural numbers with each one being less than \((k + 1)\text{.}\) That is, there exist natural numbers \(a\) and \(b\) with

\begin{equation*} k + 1 = a \cdot b, \qquad \text{ and } \qquad 1 \lt a \leq k \text{ and } 1 \lt b \leq k\text{.} \end{equation*}

Using the inductive assumption, this means that \(P (a)\) and \(P (b)\) are both true. Consequently, \(a\) and \(b\) are prime numbers or are products of prime numbers. Since \(k + 1 = a \cdot b\text{,}\) we conclude that \((k + 1)\) is a product of prime numbers. That is, we conclude that \(P (k + 1)\) is true. This proves the inductive step.

Hence, by the Second Principle of Mathematical Induction, we conclude that \(P (n)\) is true for all \(n \in \N\) with \(n \geq 2\text{,}\) and this means that each natural number greater than 1 is either a prime number or is a product of prime numbers.