1.1: The Well-Ordering Principle and Mathematical Induction

\(\newcommand{\NN}{\mathbb N}\)
\(\newcommand{\RR}{\mathbb R}\)
\(\newcommand{\QQ}{\mathbb Q}\)
\(\newcommand{\ZZ}{\mathbb Z}\)
\(\newcommand{\Cc}{\mathcal C}\)
\(\newcommand{\Dd}{\mathcal D}\)
\(\newcommand{\Ee}{\mathcal E}\)
\(\newcommand{\Ff}{\mathcal F}\)
\(\newcommand{\Kk}{\mathcal K}\)
\(\newcommand{\Mm}{\mathcal M}\)
\(\newcommand{\Pp}{\mathcal P}\)
\(\newcommand{\ind}{\operatorname{ind}}\)
\(\newcommand{\ord}{\operatorname{ord}}\)

The Well-Ordering Principle

Given a set \(S\) of numbers (of any kind), we say that \(\ell\in S\) is a least element of \(S\) if \(\forall x\in S\), either \(x=\ell\) or \(\ell<x\).

Definition: The Well-Ordering Principle

Every non-empty set of natural numbers has a least element.

This principle is often taken as an axiom.

The Pigeonhole Principle

Theorem \(\PageIndex{1}\): The Pigeonhole Principle

Let \(s,k\in\NN\) satisfy \(s>k\). If \(s\) objects are placed in \(k\) boxes, then at least one box contains more than one object.

Proof

Suppose that none of the boxes contains more than one object. Then there are at most \(k\) objects. This leads to a contradiction with the fact that there are \(s\) objects for \(s>k\).

The Principle of Mathematical Induction

We now present a valuable tool for proving results about integers. This tool is the principle of mathematical induction.

Theorem \(\PageIndex{2}\): The First Principle of Mathematical Induction

Let \(S\subset\NN\) be a set satisfying the following two properties:

1. \(1\in S\); and
2. \(\forall k\in\NN,\ k\in S\Rightarrow k+1\in S\).

Then \(S=\NN\). More generally, if \(\Pp(n)\) is a property of natural numbers which may or may not be true for any particular \(n\in\NN\), satisfying

1. \(\Pp(1)\) is true; and
2. \(\forall k\in\NN,\ \Pp(k)\Rightarrow\Pp(k+1)\)

then \(\forall n\in\NN, \Pp(n)\) is true.

Proof

We use the well-ordering principle to prove this first principle of mathematical induction.

Let \(S\) be the set from the first part of the theorem and let \(T\) be the set of natural numbers not in \(S\). We will use a proof by contradiction, so assume \(T\) is non-empty.

Then, by the well-ordering principle, \(T\) contains a least element \(\ell\).

Note that \(1\in S\), so \(1\notin T\) and thus \(\ell>1\). Therefore \(\ell-1\) is a natural number. Since \(\ell\) is the least element of \(T\), \(\ell-1\) is not in \(T\), it is therefore in \(S\).

But by the defining properties of \(S\), since \(\ell-1\in S\), \(\ell=\ell-1+1\in S\), which contradicts the fact that \(\ell\) is a least element of \(T\), so in \(T\), so not in \(S\).

This contradiction implies that the assumption that \(T\) is non-empty is false, hence \(S=\NN\).

For the second part of the theorem, let \(S=\{n\in\NN\mid\Pp(n)\text{\ is true}\}\) and apply the first part.

Example \(\PageIndex{1}\)

We use mathematical induction to show that \(\forall n\in \mathbb{N}\) \[\sum_{j=1}^nj=\frac{n(n+1)}{2}.\] First note that \[\sum_{j=1}^1j=1=\frac{1\cdot 2}{2}\] and thus the the statement is true for \(n=1\). For the remaining inductive step, suppose that the formula holds for some particular \(n\in\NN\), that is \(\sum_{j=1}^nj=\frac{n(n+1)}{2}\). We show that \[\sum_{j=1}^{n+1}j=\frac{(n+1)(n+2)}{2}.\] to complete the proof by induction. Indeed \[\sum_{j=1}^{n+1}j=\sum_{j=1}^nj+(n+1)=\frac{n(n+1)}{2}+(n+1)=\frac{(n+1)(n+2)}{2},\] and the result follows.

Example \(\PageIndex{2}\)

Now we use mathematical induction to prove that \(n!\leq n^n\) \(\forall n\in\NN\).

Note that \(1!=1\leq 1^1=1\). We now present the inductive step. Suppose that \[n!\leq n^n\] for some \(n\in\NN\), we prove that \((n+1)!\leq (n+1)^{n+1}\). Note that \[(n+1)!=(n+1)n!\leq (n+1).n^n<(n+1)(n+1)^{n}=(n+1)^{n+1}.\] This completes the proof.

Theorem \(\PageIndex{3}\): The Second Principle of Mathematical Induction

Let \(S\subset\NN\) be a set satisfying the following two properties:

1. \(1\in S\); and
2. \(\forall k\in\NN,\ 1,\dots,k\in S\Rightarrow k+1\in S\).

Then \(S=\NN\). More generally, if \(\Pp(n)\) is a property of natural numbers which may or may not be true for any particular \(n\in\NN\), satisfying

1. \(\Pp(1)\) is true; and
2. \(\forall k\in\NN,\) if \(\Pp(1),\dots,\Pp(k)\) are all true, then \(\Pp(k+1)\) is also true

then \(\forall n\in\NN, \Pp(n)\) is true.

Proof

To prove the second principle of induction, we use the first principle of induction.

Let \(S\) be a set of integers as in the first part of the theorem. For \(n\in\NN\), let \(\Pp(n)\) be the mathematical property “\(1,\dots,n\in S\)”. Then we can apply the First Principle of Mathematical Induction to prove that \(\forall n\in\NN\ \Pp(n)\) is true, which means \(S=\NN\). [Details left to the reader.]

The second part of the theorem follows from the first in exactly the same way that the second part of the First Principle of Mathematical Induction followed from the first.

Exercise \(\PageIndex{1}\)

1. Prove using mathematical induction that \(n<3^n\) for all positive integers \(n\).
2. Show that \(\sum_{j=1}^nj^2=\frac{n(n+1)(2n+1)}{6}\).
3. Use mathematical induction to prove that \(\sum_{j=1}^n(-1)^{j-1}j^2= \dfrac{(-1)^{n-1}n(n+1)}{2}\).
4. Use mathematical induction to prove that \(\sum_{j=1}^nj^3= \left[\dfrac{n(n+1)}{2} \right]^2\) for every positive integer \(n\).
5. Use mathematical induction to prove that \(\sum_{j=1}^n(2j-1)=n^2\).
6. Use mathematical induction to prove that \(2^n<n!\) for \(n\geq 4\).
7. Use mathematical induction to prove that \(n^2<n!\) for \(n\geq 4\).