Suppose we wish to show that
\begin{equation*}1 + 2 + \cdots + n = \frac{n(n + 1)}{2}\end{equation*}
for any natural number \(n\). This formula is easily verified for small numbers such as \(n = 1\), 2, 3, or 4, 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
\begin{equation*}1 = \frac{1(1 + 1)}{2}.\end{equation*}
If we have verified the first \(n\) cases, then
\begin{align*}
1 + 2 + \cdots + n + (n + 1) & = \frac{n(n + 1)}{2} + n + 1\\
& = \frac{n^2 + 3n + 2}{2}\\
& = \frac{(n + 1)[(n + 1) + 1]}{2}.
\end{align*}
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.

#####
Principle2.1First 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\). If for all integers \(k\) with \(k \geq n_0\), \(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\).

#####
Example2.2

For all integers \(n \geq 3\), \(2^n \gt n + 4\). Since
\begin{equation*}8 = 2^3 \gt 3 + 4 = 7,\end{equation*}
the statement is true for \(n_0 = 3\). Assume that \(2^k \gt k + 4\) for \(k \geq 3\). Then \(2^{k + 1} = 2 \cdot 2^{k} \gt 2(k + 4)\). But
\begin{equation*}2(k + 4) = 2k + 8 \gt k + 5 = (k + 1) + 4\end{equation*}
since \(k\) is positive. Hence, by induction, the statement holds for all integers \(n \geq 3\).

#####
Example2.3

Every integer \(10^{n + 1} + 3 \cdot 10^n + 5\) is divisible by 9 for \(n \in {\mathbb N}\). For \(n = 1\),
\begin{equation*}10^{1 + 1} + 3 \cdot 10 + 5 = 135 = 9 \cdot 15\end{equation*}
is divisible by 9. Suppose that \(10^{k + 1} + 3 \cdot 10^k + 5\) is divisible by 9 for \(k \geq 1\). Then
\begin{align*}
10^{(k + 1) + 1} + 3 \cdot 10^{k + 1} + 5& = 10^{k + 2} + 3 \cdot 10^{k + 1} + 50 - 45\\
& = 10 (10^{k + 1} + 3 \cdot 10^{k} + 5) - 45
\end{align*}
is divisible by 9.

#####
Example2.4

We will prove the binomial theorem using mathematical induction; that is,
\begin{equation*}(a + b)^n = \sum_{k = 0}^{n} \binom{n}{k} a^k b^{n - k},\end{equation*}
where \(a\) and \(b\) are real numbers, \(n \in \mathbb{N}\), and
\begin{equation*}\binom{n}{k} = \frac{n!}{k! (n - k)!}\end{equation*}
is the binomial coefficient. We first show that
\begin{equation*}\binom{n + 1}{k} = \binom{n}{k} + \binom{n}{k - 1}.\end{equation*}
This result follows from
\begin{align*}
\binom{n}{k} + \binom{n}{k - 1} & = \frac{n!}{k!(n - k)!} +\frac{n!}{(k-1)!(n - k + 1)!}\\
& = \frac{(n + 1)!}{k!(n + 1 - k)!}\\
& =\binom{n + 1}{k}.
\end{align*}
If \(n = 1\), the binomial theorem is easy to verify. Now assume that the result is true for \(n\) greater than or equal to 1. Then
\begin{align*}
(a + b)^{n + 1} & = (a + b)(a + b)^n\\
& = (a + b) \left( \sum_{k = 0}^{n} \binom{n}{k} a^k b^{n - k}\right)\\
& = \sum_{k = 0}^{n} \binom{n}{k} a^{k + 1} b^{n - k} + \sum_{k = 0}^{n} \binom{n}{k} a^k b^{n + 1 - k}\\
& = a^{n + 1} + \sum_{k = 1}^{n} \binom{n}{k - 1} a^{k} b^{n + 1 - k} + \sum_{k = 1}^{n} \binom{n}{k} a^k b^{n + 1 - k} + b^{n + 1}\\
& = a^{n + 1} + \sum_{k = 1}^{n} \left[ \binom{n}{k - 1} + \binom{n}{k} \right]a^k b^{n + 1 - k} + b^{n + 1}\\
& = \sum_{k = 0}^{n + 1} \binom{n + 1}{k} a^k b^{n + 1- k}.
\end{align*}

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

#####
Principle2.5Second 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\). If \(S(n_0), S(n_0 + 1), \ldots, S(k)\) imply that \(S(k + 1)\) for \(k \geq n_0\), then the statement \(S(n)\) is true for all integers \(n \geq n_0\).

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.

#####
Principle2.6Principle 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.

#####
Lemma2.7

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

Let \(S = \{ n \in {\mathbb N} : n \geq 1 \}\). Then \(1 \in S\). Assume that \(n \in S\). Since \(n+1 \geq 1\), \(n + 1 \in S\); hence, by induction, \(S =\mathbb N\) and every natural number is greater than or equal to 1.

#####
Theorem2.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\), then \(S\) contains a least element. We will show that if a set \(S\) contains an integer less than or equal to \(n + 1\), then \(S\) has a least element. If \(S\) does not contain an integer less than \(n+1\), then \(n+1\) is the smallest integer in \(S\). Otherwise, since \(S\) is nonempty, \(S\) must contain an integer less than or equal to \(n\). 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!\), the factorial of a positive integer \(n\).

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