## Section 2.1 Mathematical Induction

Suppose we wish to show that

for any natural number \(n\text{.}\) This formula is easily verified for small numbers such as \(n = 1\text{,}\) \(2\text{,}\) \(3\text{,}\) or \(4\text{,}\) but it is impossible to verify for all natural numbers on a case-by-case basis. To prove the formula true in general, a more generic method is required.

Suppose we have verified the equation for the first \(n\) cases. We will attempt to show that we can generate the formula for the \((n + 1)\)th case from this knowledge. The formula is true for \(n = 1\) since

If we have verified the first \(n\) cases, then

This is exactly the formula for the \((n + 1)\)th case.

This method of proof is known as mathematical induction. Instead of attempting to verify a statement about some subset \(S\) of the positive integers \({\mathbb N}\) on a case-by-case basis, an impossible task if \(S\) is an infinite set, we give a specific proof for the smallest integer being considered, followed by a generic argument showing that if the statement holds for a given case, then it must also hold for the next case in the sequence. We summarize mathematical induction in the following axiom.

###### Principle 2.1. First Principle of Mathematical Induction.

Let \(S(n)\) be a statement about integers for \(n \in {\mathbb N}\) and suppose \(S(n_0)\) is true for some integer \(n_0\text{.}\) If for all integers \(k\) with \(k \geq n_0\text{,}\) \(S(k)\) implies that \(S(k+1)\) is true, then \(S(n)\) is true for all integers \(n\) greater than or equal to \(n_0\text{.}\)

###### Example 2.2.

For all integers \(n \geq 3\text{,}\) \(2^n \gt n + 4\text{.}\) Since

the statement is true for \(n_0 = 3\text{.}\) Assume that \(2^k \gt k + 4\) for \(k \geq 3\text{.}\) Then \(2^{k + 1} = 2 \cdot 2^{k} \gt 2(k + 4)\text{.}\) But

since \(k\) is positive. Hence, by induction, the statement holds for all integers \(n \geq 3\text{.}\)

###### Example 2.3.

Every integer \(10^{n + 1} + 3 \cdot 10^n + 5\) is divisible by \(9\) for \(n \in {\mathbb N}\text{.}\) For \(n = 1\text{,}\)

is divisible by \(9\text{.}\) Suppose that \(10^{k + 1} + 3 \cdot 10^k + 5\) is divisible by \(9\) for \(k \geq 1\text{.}\) Then

is divisible by \(9\text{.}\)

###### Example 2.4.

We will prove the binomial theorem using mathematical induction; that is,

where \(a\) and \(b\) are real numbers, \(n \in \mathbb{N}\text{,}\) and

is the binomial coefficient. We first show that

This result follows from

If \(n = 1\text{,}\) the binomial theorem is easy to verify. Now assume that the result is true for \(n\) greater than or equal to \(1\text{.}\) Then

We have an equivalent statement of the Principle of Mathematical Induction that is often very useful.

###### Principle 2.5. Second Principle of Mathematical Induction.

Let \(S(n)\) be a statement about integers for \(n \in {\mathbb N}\) and suppose \(S(n_0)\) is true for some integer \(n_0\text{.}\) If \(S(n_0), S(n_0 + 1), \ldots, S(k)\) imply that \(S(k + 1)\) for \(k \geq n_0\text{,}\) then the statement \(S(n)\) is true for all integers \(n \geq n_0\text{.}\)

A nonempty subset \(S\) of \({\mathbb Z}\) is well-ordered if \(S\) contains a least element. Notice that the set \({\mathbb Z}\) is not well-ordered since it does not contain a smallest element. However, the natural numbers are well-ordered.

###### Principle 2.6. Principle of Well-Ordering.

Every nonempty subset of the natural numbers is well-ordered.

The Principle of Well-Ordering is equivalent to the Principle of Mathematical Induction.

###### Lemma 2.7.

The Principle of Mathematical Induction implies that \(1\) is the least positive natural number.

###### Proof.

Let \(S = \{ n \in {\mathbb N} : n \geq 1 \}\text{.}\) Then \(1 \in S\text{.}\) Assume that \(n \in S\text{.}\) Since \(0 \lt 1\text{,}\) it must be the case that \(n = n + 0 \lt n + 1\text{.}\) Therefore, \(1 \leq n \lt n + 1\text{.}\) Consequently, if \(n \in S\text{,}\) then \(n + 1\) must also be in \(S\text{,}\) and by the Principle of Mathematical Induction, and \(S = \mathbb N\text{.}\)

###### Theorem 2.8.

The Principle of Mathematical Induction implies the Principle of Well-Ordering. That is, every nonempty subset of \(\mathbb N\) contains a least element.

###### Proof.

We must show that if \(S\) is a nonempty subset of the natural numbers, then \(S\) contains a least element. If \(S\) contains 1, then the theorem is true by Lemma 2.7. Assume that if \(S\) contains an integer \(k\) such that \(1 \leq k \leq n\text{,}\) then \(S\) contains a least element. We will show that if a set \(S\) contains an integer less than or equal to \(n + 1\text{,}\) then \(S\) has a least element. If \(S\) does not contain an integer less than \(n+1\text{,}\) then \(n+1\) is the smallest integer in \(S\text{.}\) Otherwise, since \(S\) is nonempty, \(S\) must contain an integer less than or equal to \(n\text{.}\) In this case, by induction, \(S\) contains a least element.

Induction can also be very useful in formulating definitions. For instance, there are two ways to define \(n!\text{,}\) the factorial of a positive integer \(n\text{.}\)

The

*explicit*definition: \(n! = 1 \cdot 2 \cdot 3 \cdots (n - 1) \cdot n\text{.}\)The

*inductive*or*recursive*definition: \(1! = 1\) and \(n! = n(n - 1)!\) for \(n \gt 1\text{.}\)

Every good mathematician or computer scientist knows that looking at problems recursively, as opposed to explicitly, often results in better understanding of complex issues.