3 Mathematical Induction

We will often use induction as a method of proof. Induction allows one to prove generalizations over a set of objects that can be ordered by the natural numbers. We will, for example, prove generalizations over proofs by induction on the number of steps they involve. Because natural numbers are defined inductively from $0$ and the successor operation, they are similarly governed by a principle of induction:

Proposition 3.1 (Simple Induction on the Natural Numbers) Given a condition $Φ$ on natural numbers, if

$0$ satisfies $Φ$ , and
a natural number $n$ satisfies $Φ$ only if its successor, $n + 1$ , satisfies $Φ$ ,

then every natural number satisfies $Φ$ .

On the other hand, since positive integers are defined inductively from $1$ and successor, they are governed by a similar principle:

Proposition 3.2 (Simple Induction on the Positive Integers) Given a condition $Φ$ on positive integers, if

$1$ satisfies $Φ$ , and
a positive integer $n$ satisfies $Φ$ only if its successor, $n + 1$ , satisfies $Φ$ ,

then every positive integer satisfies $Φ$ .

For purposes of illustration, consider the pattern below: $\begin{array}{llll} 1 & = & 1 & = & \frac{1 . (1 + 1)}{2} \\ 1 + 2 & = & 3 & = & \frac{2 . (2 + 1)}{2} \\ 1 + 2 + 3 & = & 6 & = & \frac{3 . (3 + 1)}{2} \\ \dots & = & \dots & = & \dots \end{array}$ Carl Gauss exploited when he noticed that the sum of the first $100$ positive integers is $5050$ , which is $\frac{100. (100 + 1)}{2}$ when confronted with the question in elementary school. But how general is the pattern?

Example 3.1 We use an induction on the positive integers to prove the generalization:

For every positive integer $n$ , $\sum_{k = 1}^{n} = \frac{n . (n + 1)}{2} .$

Here the condition $Φ (n)$ is: $\sum_{k = 1}^{n} = \frac{n . (n + 1)}{2}$

By induction on the positive integers, it is enough to show:

$Φ (1)$ , and $\sum_{n = 1}^{1} = \frac{1. (1 + 1)}{2}$
$Φ (n)$ only if $Φ (n + 1)$ .

That is, suppose:

$\sum_{k = 1}^{n} = \frac{n . (n + 1)}{2} .$

Then: $\sum_{k = 1}^{n + 1} = \sum_{k = 1}^{n} + (n + 1) = \frac{n . (n + 1)}{2} + (n + 1) = \frac{n^{2} + 3 n + 2}{2} = \frac{(n + 1) . ((n + 1) + 1)}{2}$ So, we conclude that every positive integer $n$ satisfies the condition.

A word of caution. Mathematical induction becomes all too powerful when it is misused. Here is an example of how a misapplication of mathematical induction can lead us astray. In the case at hand, we misuse induction to argue for the absurd claim that all finite sets have the same cardinality.

Exercise 3.1 Identify the flaw in the following argument.

Let $Φ (n)$ be the following condition on natural numbers:

no two sets with fewer than $n$ elements differ in cardinality.

We (mis)use induction to argue that the condition holds for every natural number. We proceed in two steps:

$Φ (0)$ .

Suppose two sets $A$ and $B$ have at most $0$ elements. Then. $A = \emptyset = B$ .
$Φ (n)$ only if $Φ (n + 1)$ .

Suppose $Φ (n)$ and let now $A$ and $B$ be two sets with at most $n + 1$ elements. Now, consider the sets $A^{-}$ and $B^{-}$ , which result from $A$ and $B$ , respectively, when we substract one element $a$ and $b$ from each. By inductive hypothesis, since $A^{-}$ and $B^{-}$ have at most $n$ elements, they have the same cardinality. But if they do, so will $A^{-} \cup {a}$ and $B^{-} \cup {b}$ , which are none other than $A$ and $B$ .

The conclusion of the argument is that no two finite sets differ in cardinality, which is patently false. Where exactly is the flaw in the argument?

We will sometimes rely on alternative but equivalent forms of induction:

Proposition 3.3 (Complete Induction on the Natural Numbers) Given a condition $Φ$ on natural numbers, if

$0$ satisfies $Φ$ , and
if all natural numbers $m$ less or equal to $n$ satisfy $Φ$ , then the successor $n + 1$ satisfies $Φ$ ,

then all natural numbers satisfy $Φ$ .

Equivalently:

Proposition 3.4 (Complete Induction on the Natural Numbers without a Base Case) Given a condition $Φ$ on natural numbers, if

if all natural numbers $m$ less than $n$ satisfy $Φ$ , then $n$ satisfies $Φ$ ,

then all natural numbers satisfy $Φ$ .

Notice that $Φ (0)$ will be true if the conditional above holds, since it is vacuously the case that all natural numbers less than $0$ satisfy the condition $Φ$ .