Any set of integers larger than a given number is well ordered.

This proposition claims that if a set has a lower bound which is a real number, then this set is well ordered.

Further, this proposition implies the principle of mathematical induction. The symbol \(\mathbb{Z}\) denotes the set of all integers. Note that if \(a\) is an integer, then there are no integers between \(a\) and \(a+1.\)

Theorem \(\PageIndex{1}\): Mathematical Induction
A set \(S\subseteq \mathbb{Z},\) having the property that \(a\in S\) and \(n+1\in S\) whenever \(n\in S\), contains all integers \(x\in \mathbb{Z}\) such that \(x\geq a.\)

Proof
Let \(T\) consist of all integers larger than or equal to \(a\) which are not in \(S.\) The theorem will be proved if \(T=\emptyset .\) If \(T\neq \emptyset\) then by the well ordering principle, there would have to exist a smallest element of \(T,\) denoted as \(b.\) It must be the case that \(b>a\) since by definition, \(a\notin T.\) Thus \(b\geq a+1\), and so \(b-1\geq a\) and \(b-1\notin S\) because if \(b-1\in\) \(S,\) then \(b-1+1=b\in S\) by the assumed property of \(S.\) Therefore, \(b-1\in T\) which contradicts the choice of \(b\) as the smallest element of \(T.\) (\(b-1\) is smaller.) Since a contradiction is obtained by assuming \(T\neq \emptyset ,\) it must be the case that \(T=\emptyset\) and this says that every integer at least as large as \(a\) is also in \(S\).

Mathematical induction is a very useful device for proving theorems about the integers. The procedure is as follows.

Procedure \(\PageIndex{1}\): Proof by Mathematical Induction

Suppose \(S_{n}\) is a statement which is a function of the number \(n\), for \(n=1,2,\cdots\), and we wish to show that \(S_{n}\) is true for all \(n \geq 1\). To do so using mathematical induction, use the following steps.

Base Case: Show \(S_{1}\) is true.
Assume \(S_{n}\) is true for some \(n\), which is the induction hypothesis . Then, using this assumption, show that \(S_{n+1}\) is true.
Proving these two steps shows that \(S_{n}\) is true for all \(n = 1,2,\cdots\).

We can use this procedure to solve the following examples.

Example \(\PageIndex{1}\): Proving by Induction

Prove by induction that \(\sum_{k=1}^{n}k^{2}=\displaystyle \frac{n\left( n+1\right) \left( 2n+1\right) }{6}\).

Solution

By Procedure \(\PageIndex{1}\) , we first need to show that this statement is true for \(n=1\). When \(n=1\), the statement says that

\[\begin{align*} \sum_{k=1}^{1}k^{2}&=\frac{1\left( 1+1\right) \left( 2(1)+1\right) }{6}\\[4pt] &=\frac{6}{6} \\[4pt] &=1\end{align*}\]

The sum on the left hand side also equals \(1\), so this equation is true for \(n=1\).

Now suppose this formula is valid for some \(n\geq 1\) where \(n\) is an integer. Hence, the following equation is true.

\[\sum_{k=1}^{n}k^{2}= \frac{n\left( n+1\right) \left( 2n+1\right) }{6} \label{induction1}\]

We want to show that this is true for \(n+1\).

Suppose we add \((n+1)^2\) to both sides of Equation \ref{induction1}.

\[\begin{align*} \sum_{k=1}^{n+1}k^{2}&=\sum_{k=1}^{n}k^{2}+\left( n+1\right) ^{2} \\[4pt] &=\frac{n\left( n+1\right) \left( 2n+1\right) }{6}+\left( n+1\right) ^{2}\end{align*}\]

The step going from the first to the second line is based on the assumption that the formula is true for \(n.\) Now simplify the expression in the second line,

\[\frac{n\left( n+1\right) \left( 2n+1\right) }{6}+\left( n+1\right) ^{2}\nonumber \]

This equals

\[\left( n+1\right) \left( \frac{n\left( 2n+1\right) }{6}+\left( n+1\right) \right)\nonumber \]

and

\[\frac{n\left( 2n+1\right) }{6}+\left( n+1\right) =\frac{6\left( n+1\right) +2n^{2}+n}{6}=\frac{ \left( n+2\right) \left( 2n+3\right) }{6}\nonumber \]

Therefore,

\[\sum_{k=1}^{n+1}k^{2}=\frac{ \left( n+1\right) \left( n+2\right) \left( 2n+3\right) }{6}=\frac{ \left( n+1\right) \left( \left( n+1\right) +1\right) \left( 2\left( n+1\right) +1\right) }{6}\nonumber \]

showing the formula holds for \(n+1\) whenever it holds for \(n.\) This proves the formula by mathematical induction. In other words, this formula is true for all \(n = 1, 2, \cdots\).

Consider another example.

Example \(\PageIndex{2}\): Proving an Inequality by Induction

Show that for all \(n\in \mathbb{N}\), \(\displaystyle \frac{1}{2}\cdot \displaystyle \frac{3}{4}\cdots \displaystyle \frac{2n-1}{2n}<\displaystyle \frac{1}{\sqrt{2n+1}}.\)

Solution

Again we will use the procedure given in Procedure \(\PageIndex{1}\) to prove that this statement is true for all \(n\). Suppose \(n=1\). Then the statement says \[\frac{1}{2}< \frac{1}{\sqrt{3}}\nonumber \] which is true.

Suppose then that the inequality holds for \(n.\) In other words,

\[\frac{1}{2}\cdot \frac{3}{4}\cdots \frac{2n-1}{2n} < \frac{1}{\sqrt{2n+1}}\nonumber \] is true.

Now multiply both sides of this inequality by \(\frac{2n+1}{2n+2}\). This yields

\[\frac{1}{2}\cdot \frac{3}{4}\cdots \frac{2n-1}{2n}\cdot \frac{2n+1}{2n+2}< \frac{1}{\sqrt{2n+1}}\frac{2n+1}{2n+2}=\frac{\sqrt{2n+1}}{2n+2}\nonumber \]

The theorem will be proved if this last expression is less than \(\displaystyle\frac{1}{\sqrt{2n+3}}.\) This happens if and only if

\[\left( \frac{1}{\sqrt{2n+3}}\right) ^{2}=\frac{1}{2n+3}>\frac{2n+1}{\left( 2n+2\right) ^{2}}\nonumber \]

which occurs if and only if \(\left( 2n+2\right) ^{2}>\left( 2n+3\right) \left( 2n+1\right)\) and this is clearly true which may be seen from expanding both sides. This proves the inequality.

Let’s review the process just used. If \(S\) is the set of integers at least as large as \(1\) for which the formula holds, the first step was to show \(1\in S\) and then that whenever \(n\in S,\) it follows \(n+1\in S.\) Therefore, by the principle of mathematical induction, \(S\) contains \([1,\infty )\cap \mathbb{Z} ,\) all positive integers. In doing an inductive proof of this sort, the set \(S\) is normally not mentioned. One just verifies the steps above.