$\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&}$

## Section2.1Mathematical Induction

Suppose we wish to show that

\begin{equation*} 1 + 2 + \cdots + n = \frac{n(n + 1)}{2} \end{equation*}

for any natural number $n\text{.}$ This formula is easily verified for small numbers such as $n = 1\text{,}$ 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.

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

\begin{equation*} 8 = 2^3 \gt 3 + 4 = 7, \end{equation*}

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

\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\text{.}$

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

\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\text{.}$ 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.

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}\text{,}$ 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\text{,}$ 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.

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.

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

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

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 Lemma 2.1.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.