\section{Well ordering and induction}

\label{well-ordering-section}

We begin this section with some important notation. Summation notation\index{summation notation}, written $\sum_{i=1}^{j} i$, represents a sum. Here, $i$ is called the index of the sum, and we add iterations until $i=j$. For example,
\[
\sum_{i=1}^{j} i = 1 + 2 + \ldots + j
\]
Another example:
\[
a_{11} + a_{12} + a_{13}  = \sum_{i=1}^{3} a_{1i}
\]

The following notation is a specific use of summation notation.

\begin{notation}{Summation notation}{summation}
Let $a_{ij}$ be real numbers, and suppose  $1\leq i\leq r$ while $
1\leq j\leq s$. These numbers can be listed in a rectangular array as given by
\begin{equation*}
\begin{array}{cccc}
a_{11} & a_{12} & \cdots & a_{1s} \\
a_{21} & a_{22} & \cdots & a_{2s} \\
\vdots & \vdots &  & \vdots \\
a_{r1} & a_{r2} & \cdots & a_{rs}
\end{array}
\end{equation*}

Then $\sum_{j=1}^{s}\sum_{i=1}^{r} a_{ij}$ means to first sum the numbers
in each column (using $i$ as the index) and then to add the sums which result (using $j$ as the index). Similarly,
$\sum_{i=1}^{r}\sum_{j=1}^{s} a_{ij}$ means to sum the vectors in
each row (using $j$ as the index) and then to add the sums which result (using $i$ as the index).
\end{notation}

Notice that since addition is commutative, $\sum_{j=1}^{s}\sum_{i=1}^{r} a_{ij} = \sum_{i=1}^{r}\sum_{j=1}^{s} a_{ij}$.

We now consider the main concept of this section. Mathematical induction and well ordering are two extremely important
principles in math. They are often used to prove significant things which
would be hard to prove otherwise.

\begin{definition}{Well ordered}{well-ordered}
 A set is well ordered if every nonempty subset $S$, contains a
smallest element $z$ having the property that $z\leq x$ for all $x\in S$.
\end{definition}

In particular, the set of natural numbers defined as
\begin{equation*}
\N = \set{1,2,\ldots}
\end{equation*}
is well ordered\index{well ordered}\index{mathematical induction}.

Consider the following proposition.

\begin{proposition}{Well ordered sets}{well-ordered}
Any set of integers larger than a given number is well ordered.
\end{proposition}

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\index{mathematical induction}. The symbol $\Z$ denotes the set of all
integers. Note that if $a$ is an integer, then there are no integers between
$a$ and $a+1$.

\begin{theorem}{Mathematical induction}{math-induction}
 A set $S\subseteq \Z$, having
the property that $a\in S$ and $n+1\in S$ whenever $n\in S$, contains all
integers $x\in \Z$ such that $x\geq a$.
\end{theorem}

\begin{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$.
\end{proof}

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

\begin{procedure}{Proof by mathematical induction}{math-induction}
Suppose $S_{n}$ is a statement which is a function of the number $n$, for $n=1,2,\ldots$, and
we wish to show that $S_{n}$ is true for all $n \geq 1$. To do so using mathematical induction\index{mathematical induction}, use the
following steps.
\begin{enumerate}
\item \textbf{Base Case:}\index{base case} Show $S_{1}$ is true.

\item Assume $S_{n}$ is true for some $n$, which is the \textbf{induction hypothesis}\index{induction hypothesis}. Then, using this assumption,
show that $S_{n+1}$ is true.
\end{enumerate}

Proving these two steps shows that $S_{n}$ is true for all $n = 1,2,\ldots$.
\end{procedure}

We can use this procedure to solve the following examples.

\begin{example}{Proving by induction}{proof-by-induction}
Prove by induction that $\sum_{k=1}^{n}k^{2}=\displaystyle
\frac{n(n+1) (2n+1) }{6}$.
\end{example}

\begin{solution}
By Procedure~\ref{proc:math-induction}, we first need to show that this statement is true for $n=1$.
When $n=1$, the statement says that
\begin{eqnarray*}
\sum_{k=1}^{1}k^{2}&=&\frac{1(1+1) (2(1)+1) }{6}\\
&=&\frac{6}{6} \\
&=& 1
\end{eqnarray*}
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.
\begin{equation}
\sum_{k=1}^{n}k^{2}=
\frac{n(n+1) (2n+1) }{6}
\label{induction1}
\end{equation}
We want to show that this is true for $n+1$.

Suppose we add $(n+1)^2$ to both sides of equation {\eqref{induction1}}.
\begin{eqnarray*}
\sum_{k=1}^{n+1}k^{2}&=&\sum_{k=1}^{n}k^{2}+(n+1) ^{2} \\
&=&\frac{n(n+1) (2n+1) }{6}+(n+1) ^{2}
\end{eqnarray*}
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,
\begin{equation*}
\frac{n(n+1) (2n+1) }{6}+(n+1) ^{2}
\end{equation*}
This equals
\begin{equation*}
(n+1) (\frac{n(2n+1) }{6}+(n+1)
)
\end{equation*}
and
\begin{equation*}
\frac{n(2n+1) }{6}+(n+1) =\frac{6(n+1)
+2n^{2}+n}{6}=\frac{\allowbreak (n+2) (2n+3) }{6}
\end{equation*}
Therefore,
\begin{equation*}
\sum_{k=1}^{n+1}k^{2}=\frac{\allowbreak (n+1) (n+2)
(2n+3) }{6}=\frac{\allowbreak (n+1) ((
n+1) +1) (2(n+1) +1) }{6}
\end{equation*}
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, \ldots$.
\end{solution}

Consider another example.

\begin{example}{Proving an inequality by induction}{inequality-proof-by-induction}
Show that for all $n\in \N$, $\displaystyle \frac{1}{2}\cdot
\displaystyle \frac{3}{4}\cdot\ldots\cdot\displaystyle \frac{2n-1}{2n}<\displaystyle
\frac{1}{\sqrt{2n+1}}$.
\end{example}

\begin{solution}
Again we will use the procedure given in Procedure~\ref{proc:math-induction} to prove that this statement is true for all $n$.
Suppose $n=1$. Then the statement says
\begin{equation*}
\frac{1}{2}< \frac{1}{\sqrt{3}}
\end{equation*}
 which is true.

Suppose then that
the inequality holds for $n$. In other words,
\begin{equation*}
 \frac{1}{2}\cdot \frac{3}{4}\cdot\ldots\cdot \frac{2n-1}{2n} < \frac{1}{\sqrt{2n+1}}
\end{equation*}
is true.

Now multiply both sides of this inequality by $\frac{2n+1}{2n+2}$.
This yields
\begin{equation*}
\frac{1}{2}\cdot \frac{3}{4}\cdot\ldots\cdot \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}
\end{equation*}
The theorem will be proved if this last expression is less than $
\displaystyle\frac{1}{\sqrt{2n+3}}$. This happens if and only if
\begin{equation*}
\paren{\frac{1}{\sqrt{2n+3}}} ^{2}=\frac{1}{2n+3}>\frac{2n+1}{(
2n+2) ^{2}}
\end{equation*}
which occurs if and only if $(2n+2) ^{2}>(2n+3)
(2n+1) $ and this is clearly true which may be seen from
expanding both sides. This proves the inequality.
\end{solution}

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 \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.
