The Principle of Mathematical Induction

If you have ever made a domino line (like the one made out of books in the video below), you are familiar with the general idea behind mathematical induction.

In order to get all of the dominoes to fall, two things need to happen:

  1. The first domino must fall.

  2. The dominos must be setup so that if any single domino falls, say the $k^{th}$ one in line, then we know that the next one in the line -- the $(k+1)^{th}$ one in line -- will also fall.

Suppose we are trying to prove some statement $S(n)$ is true for every positive integer $n$. For example, maybe $S(n)$ is the statement "The sum of the first $n$ positive odd numbers is $n^2$. For any given value of $n$, $S(n)$ might be trivial to verify. Certainly it is easy to check (via simple arithmetic) the aforementioned statement is true for any individual value of $n$:

$$\begin{array}{rlcl}
S(1):& 1 &=& 1^2 \quad \quad \textrm{...clearly this is true;}\\
S(3):& 1 + 3 + 5 &=& 3^2 \quad \quad \textrm{...this works too;}\\
S(10):& 1 + 3 + 5 + 7 + 9 + 11 + 13 &=& 7^2 \quad \quad \textrm{...more arithmetic, but it checks out!}
\end{array}$$

However, we desire to show that this works for all positive integers $n$. We can't check every possibility via arithmetic -- there are infinitely many possibilities!

Instead, we think of each $S(n)$ as a domino that either falls or doesn't fall, according to whether $S(n)$ is true or not true.

We may then reasonably conclude that $S(n)$ is true for every positive integer $n$ (i.e., all of the dominoes fall), if we know:

  1. $S(1)$ is true (i.e., the first domino falls); and

  2. If $S(k)$ is true for any particular value of $k$, then $S(k+1)$ must also be true (i.e., if the $k^{th}$ domino falls, then the $(k+1)^{th}$ domino must also fall).

Formalizing the above method of argument, by removing the references to dominoes, we have:

The Principle of Mathematical Induction.
If, for any statement involving a positive integer, $n$, the following are true:

  1. The statement holds for $n=1$, and
  2. Whenever the statement holds for $n=k$, it must also hold for $n=k+1$

then the statement holds for for all positive integers, $n$.

In an inductive argument, demonstrating the first condition above holds is called the basis step, while demonstrating the second is called the inductive step. Further, the assumption that the statement holds for $n=k$ for some particular value of $k$ that is necessary to demonstrate the inductive step is called the inductive hypothesis.

There are several variations on this theme. For example, one can argue (inductively) that a statement holds for all integers $n \ge n_0$ by showing that: 1) it holds when $n = n_0$; and 2) when it holds for some $n=k$, it must also hold for $n=k+1$.

Alternatively, one could argue that a statement holds for all positive even integers by showing that: 1) it holds when $n=2$; and 2) when it holds for some $n=k$, it must also hold for $n=k+2$.

Another variant shown below, which is also called complete induction or strong induction, requires in the inductive step that we assume not only that the statement holds for $n = k$ but also that it is true for all $n \le k$.

The (Second) Principle of Mathematical Induction.

If, for any statement involving a positive integer, $n$, the following are true:

  1. The statement holds for $n=1$, and
  2. Whenever the statement holds for all $n \le k$, it must also hold for $n=k+1$

then the statement holds for all positive integers, $n$.

This second principle of mathematical induction is completely equivalent to the first (if you wish, check out the proof), but can significantly shorten the work needed in some contexts.

While it may not look like it at first blush, the following is also equivalent to the principal of mathematical induction, and can often be used in its place to create a more elegant argument.

The Well-Ordering Principle.

Every non-empty set of positive integers contains a smallest element.

Note, one could replace the words "positive integers" with "non-negative integers", or even "integers greater than some given $M \in \mathbb{Z}$", and still have an equivalent principle. Depending on what text you might read, these variations are sometimes seen.

To see the connection between the Well-Ordering Principle and the Principle of Mathematical Induction, consider the following standard way to use Well Ordering to prove that some property $P(n)$ holds for every positive integer $n$:

To prove that "$P(n)$ is true for all $n \in \mathbb{N}$" using the Well Ordering Principle:

  1. Define the set $S$ of counterexamples to $P$ being true. Namely, define $$S = \{ n \in \mathbb{N} \, : \, P(n) \textrm{ is false}\}$$
  2. Argue indirectly, and assume that $S$ is nonempty
  3. By the Well Ordering Principle, there must be a smallest element $k$ in $S$
  4. Reach a contradiction (somehow) -- often by showing how to use $k$ to find another member of $S$ that is smaller than $k$
  5. Conclude the assumption must be false, and that it is instead the case that $S$ must be empty
  6. Consequently no counterexamples exist, which means that $P(n)$ is true for all $n \in \mathbb{N}$. QED