 %!TEX root = proofs+concepts.tex







\chapter{Proof by Induction} \label{ch.induction}

\begin{quote}
\it 
Mathematicians aren't satisfied because they know there
are no solutions up to four million or four billion,
they really want to know that there are no solutions up to infinity.
\par\raggedleft \small\rm attributed to \sf Andrew Wiles (1953--), British mathematician
\end{quote}

%\begin{quote}
%\it 
%The deductive method is the mode of using knowledge, 
%\\ and the inductive method the mode of acquiring it.
%\par\raggedleft \small\rm\sf
%Henry Mayhew (1812--1887), British journalist
%\\ 
%\emph{London Labour and the London Poor}
%\end{quote}

\medskip\noindent
You are familiar with many of the properties of natural numbers, such as:
\begin{itemize}
\item the commutative laws: $x + y = y + x$ and $xy = yx$,
\item the associative laws: $(x + y) + z = x + (y + z)$ and $(xy)z = x(yz)$,
and
\item the distributive laws: $x(y+z) = xy + xz$ and $(y+z)x = yx + zx$.
\end{itemize}
These properties are also true for integers, for rational numbers, and for real numbers. 

In this \lcnamecref{ch.induction}, we discuss a very useful property of~$\natural$ that is \textbf{not} true of $\integer$ or $\rational$ or~$\real$. 
It is often very useful for proving assertions about natural numbers, and requires an understanding of sets and predicates (which were introduced in \cref{SetsChap}), but not the full theory of {\QL}.



\section{The Principle of Mathematical Induction} \label{BasicInductionSect}

\begin{remind}
To say that $P(n)$ is a \define{predicate} of natural numbers, means that, for each natural number~$n$, we have an assertion $P(n)$ that is either true or false. Some examples of predicates are:
	\begin{itemize}
	\item Let $P_{\rm odd}(n)$ be the assertion ``$n$ is odd\rlap.''
	\item Let $P_{\rm big}(n)$ be the assertion ``$n > 1000$\rlap.''
	\item Let $P_{\rm square}(n)$ be the assertion ``$\exists k \in \natural,( n = k^2 )$\rlap.''
	\item Let $P_{\rm prime}(n)$ be the assertion ``$n$~is a prime number\rlap.''
	\end{itemize}
\end{remind}

Mathematicians accept the truth of the following assertion as a basic fact about the natural numbers:

 \begin{axiom}[(\define{Principle of Mathematical Induction})] \label{InductionP(n)}
 \index{proof!by induction}\index{induction|indsee{proof by induction}}%
 Suppose $P(n)$ is a predicate of natural numbers. If
 \begin{enumerate}
  \renewcommand{\theenumi}{\roman{enumi}}
  \renewcommand{\labelenumi}{\rm(\theenumi)}
  \item \label{InductionP(n)-base} $P(1)$ is true,
 and
 \item \label{InductionP(n)-step}
for every $ k \ge 2, \bigl( P(k-1) \implies P(k) \bigr)$,
 \end{enumerate}
 then $P(n)$ is true for all $n \in \natural^+$.
 \end{axiom}


 Although we cannot \emph{prove} \cref{InductionP(n)}, it can be given an informal justification that
 may convince you to accept it as a valid property of~$\natural$: 
 
 \medskip % !!!
 \setbox0\hbox{\proofnamestyle \ref{InductionP(n)}}
 \begin{proof}[Informal justification of Axiom~\copy0] % !!!
 Let $n$ be an arbitrary element of~$\natural^+$.
 \begin{itemize}
 \item From \pref{InductionP(n)-base}, we know $P(1)$ is true.
 \item From \pref{InductionP(n)-step}, we know $P(2-1) \eif P(2)$ is true. \\
 Since $P(2-1) = P(1)$ is true, we conclude, by $\eif$-elimination, that $P(2)$ is true.
 \item From \pref{InductionP(n)-step}, we know $P(3-1) \eif P(3)$ is true. \\
 Since $P(3-1) = P(2)$ is true, we conclude, by $\eif$-elimination, that $P(3)$ is true.
% \item From \pref{InductionP(n)-step}, we know $P(4-1) \eif P(4)$ is true. \\
% Since $P(4-1) = P(3)$ is true, we conclude, by $\eif$-elimination, that $P(4)$ is true.
 \\ \hbox{\hskip 1in} $\vdots$
 \item From \pref{InductionP(n)-step}, we know $P(n-1) \eif P(n)$ is true. \\
Since $P(n-1)$ is true, we conclude, by $\eif$-elimination, that $P(n)$ is true.
 \end{itemize}
 Since $n$ is an arbitrary element of~$\natural^+$, 
 we conclude that  $P(n)$ is true for all $n \in \natural^+$.
 \end{proof}


 

\begin{terminology} \ 
\begin{itemize}
\item In a proof using Mathematical Induction, establishing~\pref{InductionP(n)-base} is called the \define{base case}\index{induction!base case|indsee{base case}}, and establishing~\pref{InductionP(n)-step} is the \define[induction!step]{induction step}.
\item In the induction step, we are proving $P(k-1) \implies P(k)$, so we assume that $P(k-1)$ is true (and establish $P(k)$). This assumption $P(k-1)$ is called the \define[induction!hypothesis]{induction hypothesis}.
\end{itemize}
\end{terminology}
 
Here is an example of how mathematical induction can be used.

\begin{prop} \label{1+...+n}
For every $n \in \natural^+$, we have
	\ $\displaystyle 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} $.
\end{prop}

\begin{proof}[Proof by induction]
 Define $P(n)$ to be the assertion
  $$ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} .$$
 
 (i) \emph{Base case.} For $n = 1$, we have 
$$1 + 2 + 3 + \cdots + n = 1 \mbox{\quad and\quad}  \frac{n(n+1)}{2}=\frac{1(1+1)}{2}=1.$$
Since these are equal,
$P(1)$ is true.

\medbreak
(ii) \emph{Induction step.} Assume $P(k-1)$ is true (and $k \ge 2$). This means that
$$ 1 + 2 + 3 + \cdots + (k-1) = \frac{(k-1)\bigl( (k-1)+1\bigr)}{2} .$$
Hence
\begin{align*}
 1 + {}&2 + 3 + \cdots + k 
 \\&= \bigl(1 + 2 + 3 + \cdots + (k-1) \bigr) + k 
\\&= \frac{(k-1)\bigl( (k-1)+1\bigr)}{2} + k && \text{(Induction Hypothesis)}
 \\&= \frac{(k-1)k}{2} + k
 \\&= k \left( \frac{k-1}{2} + 1 \right)
 \\&= k \left( \frac{k+1}{2} \right)
 \\&= \frac{k (k+1)}{2}
 , \end{align*}
 so $P(k)$ is true.  
 
 Therefore, by the Principle of Mathematical Induction, we know $P(n)$ is true for all~$n$. This means
 	$$ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} $$
for every $n \in \natural^+$.
\end{proof}

\begin{rem}
A proof by induction is often used to show that two functions $f(n)$ and $g(n)$ are equal. 
(\Cref{1+...+n} is an example of this, with $f(n) = 1+2+3+\cdots +n$ and $g(n) = n(n+1)/2$.)
The base case is usually easy: calculate $f(1)$ and $g(1)$, then notice that they are equal.
On the other hand, it is usually not immediately obvious how to do the induction step, so it is a good idea to start by doing some scratch work:
\begin{itemize}
\item Write down the desired equality $f(k) \? g(k)$. 
\item Then use algebraic simplifications to arrive at a true statement. At some point in these manipulations, you will use the induction hypothesis to replace $f(k-1)$ with $g(k-1)$, or vice-versa.
\end{itemize}
A proof can then be obtained by rewriting these algebraic steps in a logical order (preferably, as a ``one-line proof'' --- a string of equalities that starts with $f(k)$ and ends with $g(k)$). 

For example, the scratch work that led to the above proof of \cref{1+...+n} can be found in \cref{1+...+nScratch} 
below. % !!! on page~\pageref{1+...+nScratch}. % !!!
In this case, the algebraic manipulations are fairly simple, but some problems are considerably more difficult.
\end{rem}

\begin{figure}[ht]
\boxit{\setbox0\vbox{
\begin{align*}
1 + 2 + 3 + \cdots + k &\? \frac{k(k+1)}{2} \\
\bigl( 1 + 2 + 3 + \cdots + (k-1) \bigr) + k &\? \frac{k(k+1)}{2} \\
\frac{(k-1) \bigl( (k-1)+1 \bigr)}{2} + k &\? \frac{k(k+1)}{2} && 
\begin{pmatrix} \text{Induction}\\ \text{Hypothesis} \end{pmatrix} \\
\frac{(k-1)k}{2} + k &\? \frac{k(k+1)}{2} \\
\left(\frac{(k-1)}{2} + 1 \right) k &\? \frac{k(k+1)}{2} \\
\left(\frac{(k+1)}{2} \right) k &\? \frac{k(k+1)}{2} & \text{\Huge $\checkmark$} 
\end{align*}
\caption{Scratch work for the proof of \cref{1+...+n}.}
\label{1+...+nScratch}
}%
\hbox to 0pt{\vbox to 0pt{\vss\color{figurecolor}\hrule width\wd0 height\ht0 depth\dp0}\hss}%
\copy0
}
\end{figure}

Here is another example that is fairly straightforward:

\begin{prop} 
For every $n \in \natural^+$, we have
	$$ 3 + 7 + 11 + \cdots + (4n-1) = 2n^2 + n .$$
\end{prop}

\begin{proof}[Proof by induction]
 Define $P(n)$ to be the assertion
 $$ 3 + 7 + 11 + \cdots + (4n-1) = 2n^2 + n .$$
 
 (i) \emph{Base case.} For $n = 1$, we have 
$$3 + 7 + 11 + \cdots + (4n-1) = 3 \mbox{\quad and\quad}  2n^2 + n = 2(1^2) + 1 = 3.$$
Since these are equal,
$P(1)$ is true.

\medbreak
(ii) \emph{Induction step.} Assume $P(k-1)$ is true (and $k \ge 2$). This means that
$$ 3 + 7 + 11 + \cdots + \bigl(4(k-1)-1 \bigr) = 2(k-1)^2 + (k-1) .$$
Hence
\begin{align*}
 3 +  {}&7 + 11 + \cdots + (4k-1)
 \\&= \Bigl( 3 +  7 + 11 + \cdots + \bigl(4(k-1)-1\bigr) \Bigr) + (4k-1)
\\&= \Bigl( 2(k-1)^2 + (k-1) \Bigr)  + (4k-1) && \text{(Induction Hypothesis)}
\\&= \Bigl( 2(k^2 - 2k + 1) + (k-1) \Bigr)  + (4k-1)
\\&= (2k^2 - 4k + 2) + (k-1)  + (4k-1)
\\&= 2k^2 + k
 , \end{align*}
 so $P(k)$ is true. 
 
 \medbreak
 
 Therefore, by the Principle of Mathematical Induction, we know $P(n)$ is true for all~$n$. This means
 	$$ 3 + 7 + 11 + \cdots + (4n-1) = 2n^2 + n $$
for every $n \in \natural^+$.
\end{proof}

\vbox{
\begin{exers} \label{InductionExers}
  Prove each formula by Mathematical Induction.
\begin{enumerate}
\item \label{InductionExers-SumEven}
 $2 + 4 + 6 + 8 + \cdots + 2n = n(n+1)$.
\item \label{InductionExers-SumOdd}
 $1 + 3 + 5 + 7 + \cdots + (2n-1) = n^2$.
\item \label{InductionExers-Sum(5n-3)}
 $\displaystyle 2 + 7 + 12 + 17 + \cdots + (5n-3) = \frac{n(5n-1)}{2}$.
\end{enumerate}
\end{exers}
}

 \begin{notation}
 It is often necessary to add up a long list of numbers (as in the above exercises), so it is convenient to have a good notation for this: if $a_1,a_2,\ldots,a_n$ is any sequence of numbers, then the sum $a_1 + a_2 + \cdots + a_n$ can be denoted by 
 $$ \sum_{k=1}^n a_k 
 \nindex{$\sum_{k=1}^n a_k$}
 .$$
 (The symbol $\sum$ is a capital sigma, the Greek version of the letter~$S$ --- it stands for ``sum\rlap.'')
 \end{notation}
 
 \begin{eg} \label{InductionSigmaEg}
  Let $a_1,a_2,\ldots,a_n$ be a sequence of numbers. Then:
 \begin{enumerate}
 \item \label{SigmaEg-a1}
  $\displaystyle\sum_{k=1}^1 a_k = a_1$,
 \qquad $\displaystyle\sum_{k=1}^2 a_k = a_1 + a_2$,
  \qquad  and 
  \qquad  $\displaystyle\sum_{k=1}^3 a_k = a_1 + a_2 + a_3$.
 \item $\displaystyle\sum_{k=1}^{1} k = 1$,
  \qquad  $\displaystyle\sum_{k=1}^{2} k = 1 + 2 = 3$,
  \qquad $\displaystyle\sum_{k=1}^{3} k = 1 + 2 + 3 = 6$.
 \item $\displaystyle\sum_{k=1}^{n} k = 1 + 2 + 3 + \cdots + n$.
 \item \label{SigmaEg-recursive}
  For any $n \in \natural^+$, we have 
 $\displaystyle\sum_{k=1}^{n} a_k = \left(\displaystyle\sum_{k=1}^{n-1} a_k \right) + a_n$. 
 \end{enumerate}
 \end{eg}

\begin{exers} \label{pr.InductionSigma} \ 
\begin{enumerate}
\item \label{pr.InductionSigma-WriteSigma}
 In \cref{InductionExers}, the left-hand side of each formula is a sum. Write each of these sums in $\sum$-notation.
\item \label{pr.InductionSigma-NoSum}
 Show that \pref{SigmaEg-a1} and \pref{SigmaEg-recursive} of \cref{SigmaEg} imply $\displaystyle\sum_{k=1}^{0} a_k = 0$.
\end{enumerate}
\end{exers}



\begin{rem}
In the Induction Step of a proof by induction, we wish to prove 
	$$ \forall k \ge 2, \bigl( P(k-1) \implies P(k) \bigr) .$$
Since $k$~is a bound (``dummy'') variable in this assertion, there is no harm in replacing it with a different letter: for example, if you prefer, it is perfectly acceptable to prove, say,
	$$ \hbox{$\forall i \ge 2, \bigl( P(i-1) \implies P(i) \bigr)$,
	\quad or \quad
	$\forall n \ge 2, \bigl( P(n-1) \implies P(n) \bigr)$%
	.}$$
This is important to keep in mind when the variable~$k$ is already being used for something else.
\end{rem}

\begin{eg} \label{InductionSigmaEg}%
Show that
	\ $\displaystyle \sum_{k=1}^n (2k - 5) = n^2 - 4n $.
\end{eg}

\begin{proof}[Proof by induction]
Define $P(n)$ to be the assertion
	$$ \sum_{k=1}^n (2k - 5) = n^2 - 4n .$$
 
 (i) \emph{Base case.} For $n = 1$, we have 
	$$ \sum_{k=1}^n (2k - 5) = \sum_{k=1}^1 (2k - 5) = 2(1) - 5 = -3 = 1^2 - 4(1) = n^2 - 4n.$$
So $P(1)$ is true.

\medbreak
(ii) \emph{Induction step.} Assume $n \ge 2$ and $P(n-1)$ is true. This means that
	$$ \sum_{k=1}^{n-1} (2k - 5) = (n-1)^2 - 4(n-1) .$$
Hence
	\begin{align*}
	\sum_{k=1}^n (2k - 5) 
	&= \left( \sum_{k=1}^{n-1} (2k - 5) \right) + (2n-5)
	\\&= \bigl( (n-1)^2 - 4(n-1) \bigr) + (2n-5) && \text{(Induction Hypothesis)}
	\\&= \bigl( (n^2-2n + 1) - 4n + 4 \bigr) + (2n-5)
	\\&= n^2-4n
	 , \end{align*}
so $P(n)$ is true.

\medskip

Therefore, by the Principle of Mathematical Induction, we conclude that $P(n)$ is true for every $n \in \natural^+$.
\end{proof}



\vbox{
\begin{exers} \label{InductionSigmaExers}
  Prove each formula by induction.
  \smallskip
  \begin{tasks}(2)
\task\fixtask \label{InductionSigmaExers-Sum(6k+7)}%
 $\displaystyle \sum_{k=1}^n (6k+7) = 3n^2 + 10n$.
\task\fixtask \label{InductionSigmaExers-Sum(4k-5)}%
 $\displaystyle \sum_{k=1}^n (4k-5) = 2n^2 - 3n$.
\task\fixtask \label{InductionSigmaExers-Sum(12k-19)}%
 $\displaystyle \sum_{k=1}^n (12k-19) = 6n^2 - 13n$.
\task\fixtask \label{InductionSigmaExers-Sum(3k+11)}%
 $\displaystyle \sum_{k=1}^n (3k+11) = \frac{3n^2 + 25n}{2}$.
\task\fixtask \label{InductionSigmaExers-Sum(3^n)}%
 $\displaystyle \sum_{k=1}^n 3^k = \frac{3^{n+1} - 3}{2}$.
\task\fixtask \label{InductionSigmaExers-SumGeometric}%
 $\displaystyle \sum_{k=0}^n a r^k = a \frac{r^{n+1} - 1}{r-1}$.
\task\fixtask \label{InductionSigmaExers-SumSquares}%
 $\displaystyle \sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$.
\task\fixtask \label{InductionSigmaExers-SumCubes}%
(harder)
 $\displaystyle \sum_{k=1}^n k^3 = \left(\frac{n(n+1)}{2} \right)^2$.
\end{tasks}
\end{exers}
}

%\begin{exer}
%Let $a_1,a_2,a_3,\ldots$ be a sequence of numbers. Prove by induction that, for all $n \in \natural$ and all $c \in \real$, that
%	$$ \sum_{k=1}^n c a_k = c \sum_{k=1}^n c a_k .$$
%\end{exer}

\begin{rem}
If you wish to prove that $P(k)$ is true for all~$k$, then the Principle of Induction can be applied with $k$ in the role of~$n$. This is called ``inducting on~$k$\rlap.'' Similarly, any other letter can be used in place of~$n$.
\end{rem}

\begin{eg}
Show, for all $k \in \natural^+$, that
	$$ \sum_{i=1}^k (3i^2 - 3 i + 1) = k^3 .$$
\end{eg}

\begin{proof}[Proof by induction]
Define $P(k)$ to be the assertion
	$$  \sum_{i=1}^k (3i^2 - 3 i + 1) = k^3 .$$

 (i) \emph{Base case.} For $k = 1$, we have 
	$$ \sum_{i=1}^k (3i^2 - 3 i + 1) = \sum_{i=1}^1 (3i^2 - 3 i + 1) = 3(1)^2 - 3 (1) + 1 = 1 = 1^3 = k^3.$$
So $P(1)$ is true.

\medbreak
(ii) \emph{Induction step.} Assume $k \ge 2$ and $P(k-1)$ is true. This means that
	$$ \sum_{i=1}^{k-1} (3i^2 - 3 i + 1) = (k-1)^3 .$$
Hence
	\begin{align*}
	\sum_{i=1}^k (3i^2 - 3 i + 1)
	&= \left( \sum_{i=1}^{k-1} (3i^2 - 3 i + 1) \right) + (3k^2 - 3k + 1)
	\\&= (k-1)^3 + (3k^2 - 3k + 1) && \text{(Induction Hypothesis)}
	\\&= (k^3 - 3k^2 + 3k - 1) + (3k^2 - 3k + 1)
	\\&= k^3
	 , \end{align*}
so $P(k)$ is true.

\medskip

By the Principle of Mathematical Induction, we conclude that $P(k)$ is true for all $k \in \natural^+$.
\end{proof}




\section{Other proofs by induction} \label{OtherInductionSect}

Not all proofs by induction are about sums:

\begin{eg}
Suppose $a,b,n \in \integer$, with $a \equiv b \pmod{n}$. Show 
 $a^k \equiv b^k \pmod{n}$, for all $k \in \natural^+$.
\end{eg}

\begin{proof}[Proof by induction]
We induct on~$k$. Define $P(k)$ to be the assertion
	$$ a^k \equiv b^k \pmod{n}.$$

 (i) \emph{Base case.} Since $a^1 = a$ and $b^1 = b$, the hypothesis $a \equiv b \pmod{n}$ tells us that
	$$ a^1 \equiv b^1 \pmod{n} ,$$
so $P(1)$ is true.

 (ii) \emph{Induction step.} Assume $P(k-1)$ is true.
 This means that 
 	$$a^{k-1} \equiv b^{k-1} \pmod{n} .$$
By assumption, we also have
	$$ a \equiv b \pmod{n} .$$
Exercise~\fullref{CongRespectOpsEx}{mult} tells us that the product of congruent quantities is congruent, so we can multiply the above congruences, to conclude that
	$$ (a^{k-1} )(a) \equiv ( b^{k-1}) (b) \pmod{n} .$$
In other words,
	$$ a^k \equiv b^k \pmod{n} ,$$
so $P(k)$ is true.

\medskip
Therefore, by the Principle of Mathematical Induction, $P(k)$ is true for every $k \in \natural^+$.
\end{proof}

\begin{exers} \label{InductModEx}
Prove each of the following assertions by induction.
\begin{problist}
\item \label{InductModEx-5k=5}
$5^k \equiv 5 \pmod{4}$, for every $k \in \natural^+$.
\item \label{InductModEx-n3=n}
 $n^3 \equiv n \pmod{3}$ for every $n \in \natural^+$.
\end{problist} 
\end{exers}

The Principle of Mathematical Induction is an important tool for proving things about sequences of numbers in which each term is defined from preceding terms.  (Such sequences are said to be defined ``\define[recursive definition of a sequence]{recursively}'' or ``inductively\rlap.'') Fibonacci numbers are one famous example of this. In this case, each term is the sum of the two preceding terms:

\begin{defn}
The \define[Fibonacci number]{Fibonacci numbers} $F_1,F_2,F_3,\ldots$ are defined by:
\begin{itemize}
\item $F_1 = 1$,
\item $F_2 = 1$,
and
\item $F_n = F_{n-1} + F_{n-2}$ for $n \ge 3$.
\end{itemize}
(For example, $F_3 = F_{3-1} + F_{3-2} = F_2 + F_1 = 1 + 1 = 2$.)
In general, each Fibonacci number (after~$F_2$) is the sum of the two preceding Fibonacci numbers, so
the first few Fibonacci numbers are: 
	$$\begin{array}{c||c|c|c|c|c|c|c|c}
	n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & \cdots \\
	\noalign{\hrule}
	F_n & 1 & 1 & 2 & 3 & 5 & 8 & 13 & \cdots
	\end{array}$$
 \end{defn}
 
 \begin{eg}
 Prove \ $\displaystyle \sum\limits_{k=1}^n F_k = F_{n+2} - 1$ \ for all $n \in \natural^+$.
 \end{eg}

\begin{proof}[Proof by induction]
Define $P(n)$ to be the assertion
	$$ \sum_{k=1}^n F_k = F_{n+2} - 1 .$$

\medskip

(i) \emph{Base case.} For $n = 1$, we have
$$ \sum_{k=1}^n F_k = \sum_{k=1}^1 F_k = F_1 = 1 = 2 - 1 = F_3 - 1 = F_{1+2} - 1 = F_{n+2} - 1,$$
so $P(1)$ is true.

\medskip
(ii) \emph{Induction step.} Assume $P(n-1)$ is true (and $n \ge 2$). Then
\begin{align*}
\sum_{k=1}^n F_k
&= \left( \sum_{k=1}^{n-1} F_k \right) + F_n
\\&= \Bigl( F_{(n-1)+2} - 1 \Bigr) + F_n && \text{(Induction Hypothesis)}
\\&= (F_{n+1} - 1) + F_n 
\\&= (F_{n+1} + F_n) - 1
\\&= F_{n+2} - 1 
&& \begin{pmatrix} \text{definition of} \\ \text{Fibonacci number} \end{pmatrix} 
.  \end{align*}

\medskip
Therefore, by the Principle of Mathematical Induction, $P(n)$ is true for every~$n$. This means
$\displaystyle \sum\limits_{k=1}^n F_k = F_{n+2} - 1$ for all $n \in \natural^+$.
\end{proof}



\begin{exers} \label{pr.InductionFibonacci}
Prove each assertion by induction. 
%(You may want to use one of the alternative versions presented in \cref{pr-OtherInduct}.)
\begin{problist}
\item \label{pr.InductionFibonacci-Fn^2}
 $\sum \limits_{k=1}^n F_k^2 = F_n F_{n+1}$.
%\item \label{pr.InductionFibonacci-F(n-1)F(n+1)}
% $F_{n-1} F_{n+1} = F_n^2 + (-1)^n$, for all $n \ge 2$.
%\item \label{pr.InductionFibonacci-formula}
% $\displaystyle F_n = \frac{(1 + \sqrt{5})^n - (1 - \sqrt{5})^n}{2^n \sqrt{5}}$, for all $n \in \natural^+$.
%\\ \hint{Let $\gamma = (1 + \sqrt{5})/2$ and $\overline\gamma = (1 - \sqrt{5})/2$, so $\gamma^2 = \gamma + 1$ and $\overline\gamma^2 = \overline\gamma + 1$. You wish to show $F_n = (\gamma^n - \overline\gamma^n)/\sqrt{5}$.} 
\item \label{pr.InductionFibonacci-even}
 $F_{3k}$ is even, for all $k \in \natural^+$.
\item \label{pr.InductionFibonacci-3}
 $F_{4k}$ is divisible by~$3$, for all $k \in \natural^+$.
\end{problist}
\end{exers}


Induction can also be applied to other sequences that are defined recursively:

\begin{eg}
Define a sequence $\{a_n\}$ by:
	\begin{itemize}
	\item $a_1 = 1$,
	and
	\item $a_n = 2a_{n-1} + 1$ for $n \ge 2$.
	\end{itemize}
Show $a_n = 2^n - 1$ for all $n \in \natural^+$.
\end{eg}

\begin{proof}[Proof by Induction]
Define $P(n)$ to be the assertion
	$$ a_n = 2^n - 1 . $$

 (i) \emph{Base case.} For $n = 1$, we have
 	$$ \text{$a_n = a_1 = 1$ \quad and \quad $2^n - 1 = 2^1 - 1 = 2 - 1 = 1$.} $$
Since these are equal, we know that $P(1)$ is true.

 (ii) \emph{Induction step.} Assume $P(k-1)$ is true (and $k \ge 2$).
 This means that 
 	$$a_{k-1} = 2^{k-1} - 1 .$$
Then
	\begin{align*}
	a_k 
	&= 2a_{k-1} + 1 && \text{(definition of~$a_k$)} 
	\\&= 2 \Bigl( 2^{k-1} - 1 \Bigr) + 1 && \text{(Induction Hypothesis)}
	\\&= \Bigl( 2^k  - 2 \Bigr) + 1
	\\&=2^k - 1
	, \end{align*}
so $P(k)$ is true.

\medskip
Therefore, by the Principle of Mathematical Induction, $P(n)$ is true for every $n$. This means
$a_n = 2^n - 1$ for all $n \in \natural^+$.
\end{proof}

\begin{history}
The Italian mathematician Fibonacci discovered the Fibonacci numbers in 1202, as the answer to a problem about the population growth of rabbits. Namely, assume that:
	\begin{itemize}
	\item You start with 1 pair of newborn rabbits (a male and a female).
	\item Each female gives birth to another pair of rabbits each month (a male and a female), starting when she is two months old. (And rabbits never die.)
	\end{itemize}
This means that the pairs of rabbits you have in the $n$th month consist of the pairs you already had last month, plus one new pair for each pair that you had two months ago. Therefore, if $F_n$ is the number of pairs in the $n$th month, then $F_n = F_{n-1} + F_{n-2}$. You can read more about Fibonacci numbers on \href{https://en.wikipedia.org/wiki/Fibonacci_number}{\emph{Wikipedia}}.
\end{history}

\begin{exers} \  \label{InductSeq}
\begin{tasks}[after-item-skip=\medskipamount](2) % !!!
\task\fixtask \label{InductSeq-3b}% 
Define a sequence $\{b_n\}$ by:
	\begin{itemize}
	\item $b_1 = 4$,
	and
	\item $b_n = 3b_{n-1} - 2$ for $n \ge 2$.
	\end{itemize}
Show $b_n = 3^n + 1$ for all $n \in \natural^+$.
\task\fixtask \label{InductSeq-4c}% 
Define a sequence $\{c_n\}$ by:
	\begin{itemize}
	\item $c_1 = 25$,
	and
	\item $c_n = 4 c_{n-1} + 5^n$ for $n \ge 2$.
	\end{itemize}
Show $c_n = 5^{n+1}$ for all $n \in \natural^+$.
\task\fixtask \label{InductSeq-2d}% 
Define a sequence $\{d_n\}$ by:
	\begin{itemize}
	\item $d_1 = 3$,
	and
	\item $d_n = 2 d_{n-1} - n + 2$ for $n \ge 2$.
	\end{itemize}
Show $d_n = 2^n + n$ for all $n \in \natural^+$.
\task\fixtask \label{InductSeq-5e}% 
Define a sequence $\{e_n\}$ by:
	\begin{itemize}
	\item $e_1 = 2$,
	and
	\item $e_n = 2 e_{n-1} - n + 1$ for $n \ge 2$.
	\end{itemize}
Show $e_n = n + 1$ for all $n \in \natural^+$.
\end{tasks}
\end{exers}



Induction is not only for proving that things are equal. For example, it can also be used to prove inequalities:

\begin{eg}
Prove $2^n \ge n$ for all $n \in \natural^+$.
\end{eg}

\begin{scratchwork}
	\begin{align*}
	2^n &\stackrel{?}{>} n \\
	2 \cdot 2^{n-1} &\stackrel{?}{>} n \\
	2 (n-1) &\stackrel{?}{\ge} n 
	&& \text{(Induction Hypothesis)} \\
	n &\stackrel{?}{\ge} 2 
	&& \text{\Large $\checkmark$}  
	\end{align*}
\end{scratchwork}

\begin{proof}[Proof by induction]
Define $P(n)$ to be the assertion
	$$ 2^n > n .$$

 (i) \emph{Base case.} For $n = 1$, we have
 	$$ 2^n = 2^1 = 2 > 1 = n ,$$
so $P(1)$ is true.

 (ii) \emph{Induction step.} Assume $P(n-1)$ is true (and $n \ge 2$).
 This means that 
 	$$2^{n-1} > n-1 .$$
Then
	\begin{align*}
	2^n
	&= 2 \cdot 2^{n-1}
	\\&> 2(n-1)
	&& \text{(Induction Hypothesis)}
	\\&= n + (n-2)
	\\& \ge n + 0
	&& \text{($n \ge 2$, so $n-2 \ge 0$)}
	\\& = n 
	, \end{align*}
so $P(n)$ is true.

\medskip
Therefore, by the Principle of Mathematical Induction, $P(n)$ is true for every natural number~$n$.
\end{proof}

\begin{exers} \ \label{IndIneq}
\begin{problist}
\item  \label{IndIneq-3n>3n} 
Prove $3^n \ge 3n$ for all $n \in \natural^+$.
\hint{Note that $3^n - 3^{n-1} > 3n - 3(n-1)$ if $n \ge 2$.}
\item  \label{IndIneq-(1+x)n}
Prove $(1 + x)^n \ge 1 + nx$ for all $x \in \real^+$ and all $n \in \natural^+$.
\end{problist}
\end{exers}



Here is a standard piece of advice:

\begin{suggestion}
Whenever you need to prove a statement with an $n$ in it, you should consider using induction.
\end{suggestion}

\begin{exer}[({\normalfont \emph{assumes familiarity with polynomials}})] \label{xnynbyxy}
Prove by induction on~$n$ that the polynomial $x^n - y^n$ is divisible by $x - y$, for all $n \in \natural^+$.
\hint{What is $(x - y)x^n + y (x^n - y^n)$?}
\end{exer}

\begin{exer}[({\normalfont \emph{assumes familiarity with commutative groups}})] \label{CommGrpInduct}
Suppose $(G,+)$ is a commutative group. For $g \in G$ and $n \in \natural^+$, we define $ng$ recursively, by:
	$$ \text{$1 g = g$ \quad and \quad $(n+1) g = ng + g$} .$$
Prove by induction on~$n$ that $(m+n)g = mg + ng$ for all $m,n \in \natural^+$.
\end{exer}

\begin{exer} \label{HorsesSameColourEx}
Explain what is wrong with the following famous ``proof'' that all horses have the same colour.
\end{exer}

\begin{proof}[Attempt at a proof by induction]
Define $P(n)$ to be the assertion
	$$ \text{``In every set of~$n$ horses, all of the horses have the same colour\rlap.''} $$

 
 (i) \emph{Base case.} For $n = 1$, let $H$ be any set of $n$~horses. Since $n = 1$, there is only one horse in~$H$, so it is obvious that all of the horses in~$H$ have the same colour.
 
 \medskip
 
 (ii) \emph{Induction step.} Assume, for every set of $n - 1$~horses, that all of the horses have the same colour (and $n \ge 2$). Let $H$ be any set of $n$~horses. 
 \begin{center}
\includegraphics{PDF/horse-induction-H.pdf}
\end{center}
Remove one horse~$h_1$ from~$H$ to form a set~$H_1$ of $n-1$ horses. By the induction hypothesis, we know that 
	\begin{align} \label{horseinduction-H1}
	\text{all of the horses in~$H_1$ have the same colour.}
	\end{align}
Now, remove some other horse~$h_2$ from~$H$ to form a different set~$H_2$ of $n-1$ horses. By applying the induction hypothesis again, we know that 
	\begin{align} \label{horseinduction-H2}
	\text{all of the horses in~$H_2$ have the same colour.}
	\end{align}
Now, choose $h$ to be some other horse (neither $h_1$ nor~$h_2$). Since $h \neq h_1$, we know $h \in H_1$, so, from  \pref{horseinduction-H1}, we know that all of the horses in~$H_1$ have the same colour as~$h$. Similarly, since $h \neq h_2$, we know $h \in H_2$, so, from  \pref{horseinduction-H2}, we know that all of the horses in~$H_2$ also have the same colour as~$h$.
This means all of the horses in $H_1 \cup H_2$ have the same colour (namely, the colour of horse~$h$). Since it is clear that $H = H_1 \cup H_2$ (because $H_1$ contains every horse except~$h_1$, which is in~$H_2$), we conclude that all of the horses in~$H$ have the same colour.

\medskip

By the Principle of Mathematical Induction, we conclude that, in every (finite) set of horses, all of the horses have the same colour.
\end{proof}


\begin{figure}[h]
\boxit{\setbox0\vbox{
\medskip
\begin{multicols}{2}
\begin{center}
\includegraphics{PDF/horse-induction-H1}
\\
{\sffamily All of the horses in~$H_1$ have the same colour,
\\ so they all have the same colour as horse~$h$.}
\end{center}
\columnbreak
\begin{center}
\includegraphics{PDF/horse-induction-H2}
\\
{\sffamily All of the horses in~$H_2$ have the same colour,
\\ so they all have the same colour as horse~$h$.}
\end{center}
\end{multicols}
\begin{center}
{\sffamily Since every horse is in either $H_1$ or~$H_2$, this implies that 
all of the horses \\ have the same colour as~$h$. 
So all of the horses have the same colour.}
\end{center}
\medskip}%
\hbox to 0pt{\vbox to 0pt{\vss\color{figurecolor}\hrule width\wd0 height\ht0 depth\dp0}\hss}%
\copy0
}
\end{figure}


\begin{warn}
Mathematical induction is a method that is used extensively by mathematicians and computer scientists. However, other scientists (and also philosophers) use the word ``induction'' to refer to a quite different method of reasoning: \emph{scientific induction} (or ``inductive reasoning'') is the process of deriving a general rule from specific examples. (It is the opposite of deductive reasoning, where specific conclusions are derived from general rules.) For example, a scientist might measure the length and the width of very many rectangles, and compare with the areas of the rectangles.  He or she would find that the area always came out to be the product of the length with the width. The scientist would then conclude (by inductive reasoning) that the area of every rectangle is the product of its length and its width. However, this does \emph{not} constitute a \emph{mathematical proof} of the formula for the area of a rectangle.
\end{warn}











\section{Other versions of induction} \label{StrongInductionSect}

It is sometimes difficult to apply the Principle of Mathematical Induction in the form we have stated in \cref{InductionP(n)}. The following \lcnamecref{pr-OtherInduct} provides some alternative versions that are more useful in some of those situations. All of them follow quite easily from the approach using ``well-ordering'' that will be discussed in the following \lcnamecref{WellOrderSect}. % \cref{WellOrderSect}. !!!

\begin{prop} \label{pr-OtherInduct}
 \renewcommand{\theenumii}{\roman{enumii}}
 \makeatletter\renewcommand{\p@enumii}{}\makeatother
Suppose $P(n)$ is a predicate of natural numbers, and $m \in \natural^+$.
\begin{enumerate}
\item \label{pr-OtherInduct-strong}
 {\rm(Strong induction)}
If
 \begin{enumerate}
  \item \label{InductionStrong-base} $P(1)$ is true,
 and
 \item \label{InductionStrong-step}
for every $ n \ge 2$, 
	\\ \hbox{\qquad} $\Bigl( \bigl( \mbox{for every } k \in \{1,2,\ldots,n-1\}, P(k) \bigr) \implies P(n) \Bigr)$,
 \end{enumerate}
 then $P(n)$ is true for all $n \in \natural^+$.

\item \label{pr-OtherInduct-Gen}
 {\rm(Generalized induction)}
 If
 \begin{enumerate}
  \item \label{InductionGen-base} $P(m)$ is true,
 and
 \item \label{InductionGen-step}
for every $ n > m$, $\bigl( P(n-1)  \implies P(n) \bigr)$,
 \end{enumerate}
 then $P(n)$ is true for all $n \ge m$.
 
\item \label{pr-OtherInduct-multiple}
 {\rm(Strong induction with multiple base cases)}
If
 \begin{enumerate} 
  \item \label{InductionMultiple-base} $P(k)$ is true for all $k \in \{1,2,\ldots,m\}$,
 and
 \item \label{InductionMultiple-step}
for every $ n > m$, 
\\ \hbox{\qquad} $\Bigl( \bigl( \mbox{for every } k \in \{1,2,\ldots,n-1\}, P(k) \bigr) \implies P(n) \Bigr)$,
 \end{enumerate}
 then $P(n)$ is true for all $n \in \natural^+$.

\item \label{pr-OtherInduct-n+1}
If
 \begin{enumerate}
  \item \label{pr-OtherInduct-n+1-base}
   $P(1)$ is true,
 and
 \item \label{pr-OtherInduct-n+1-step}
for every $ k \in \natural^+$, $P(k) \eif P(k+1)$,
 \end{enumerate}
 then $P(n)$ is true for all $n \in \natural^+$.

\item \label{pr-OtherInduct-set}  % was \label{InductionSet}
 Suppose $S \subset \natural^+$. If
 \begin{enumerate} \renewcommand{\theenumi}{\roman{enumi}}
  \item \label{InductionSet-base} $1 \in S$,
 and
 \item \label{InductionSet-step}
for every $n \in S, \bigl( n+1 \in S \bigr)$,
 \end{enumerate}
 then $S = \natural^+$.

 \end{enumerate}
 \end{prop}
 
 \begin{rem}
 There are many other versions of induction. For example, if you wish to prove that $P(n)$ is true for all $n \in \natural$ (rather than only for all $n \in \natural^+$), then 
 \begin{enumerate} \renewcommand{\theenumi}{\roman{enumi}}
 \item your base case would be to prove $P(0)$, and 
 \item your induction step would be to prove $P(n-1) \eif P(n)$, for all $n \ge 1$.
 \end{enumerate}
 \end{rem}



\begin{eg} \label{Fn<2nEg}
Prove $F_n < 2^n$, for every $n \in \natural^+$.
\end{eg}

\begin{proof}[Proof by induction] 
Define $P(n)$ to be the assertion
	$$ F_n < 2^n .$$
 We use strong induction with $2$~base cases.

 (i) \emph{Base cases.} 
 We have 
 	$$ F_1 = 1 < 2 = 2^1 ,$$
and 
	$$ F_2 =1 < 4 = 2^2 ,$$
so $P(1)$ and $P(2)$ are true.

 (ii) \emph{Induction step.} Assume $n \ge 3$, and that $P(n-1)$ and $P(n-2)$ are true. We have
 	\begin{align*} F_n 
	&= F_{n-1} + F_{n-2}
	\\&< 2^{n-1} + 2^{n-2} && \text{(Induction Hypotheses)}
	\\&< 2^{n-1} + 2^{n-1}
	\\&= 2^n
	, \end{align*}
so $P(n)$ is true.

By the Principle of Mathematical Induction (in the form of strong induction with multiple base cases), we conclude that $P(n)$ is true for all $n \in \natural^+$.
\end{proof}






\section{The natural numbers are well-ordered} \label{WellOrderSect}

Induction is a very powerful tool, but it is sometimes hard to apply (and there are many different versions to keep track of, as we saw in the preceding section). % !!!
 In this \lcnamecref{WellOrderSect}, we demonstrate a closely related technique that is often less cumbersome to use. 

\begin{defn}
Let $S \subset \real$ and $a \in \real$. We say $a$ is the \define[smallest element]{smallest} element of~$S$ iff:
	\begin{itemize}
	\item $a \in S$,
	and
	\item $\forall s \in S$, $a \le s$.
	\end{itemize}
\end{defn}

\begin{eg} \ 
	\begin{itemize}
	\item The smallest element of  $\{2,4,6,8\}$ is~$2$.
	\item The smallest element of  $\{12, 9, 18, 5, 13 \}$ is~$5$.
	\end{itemize}
\end{eg}

It is important to realize that not every set of numbers has a smallest element:

\begin{exer} \label{NoSmallestEx}
Show that the given set does not have a smallest element.
	\begin{enumerate}
	\item \label{NoSmallestEx-Z}
	\  \hbox to 1.75in{$\integer$ \hss}
	 \hint{If $n \in \integer$, then $n - 1 < n$.}
	\item  \label{NoSmallestEx-R+}
	\  \hbox to 1.75in{$\real^+ = \{\, x \in \real \mid x > 0 \,\}$ \hss}
	 \hint{If $x \in \real^+$, then $x/2 \in \real^+$.}
	\item\label{NoSmallestEx-empty}
	  \  \hbox to 1.75in{$\emptyset$ \hss}
	 \hint{A set with no elements cannot have a \emph{smallest} element.}
	\end{enumerate}
\end{exer}

This problem does not arise for subsets of~$\natural$:

\begin{thm}[($\pmb{\natural}$ % !!!
is \define{well-ordered})] \label{NisWO} %\index{N is well-ordered@$\natural$ is well-ordered}
Every nonempty subset of\/~$\natural$ has a smallest element.
\end{thm}

This rather obvious observation is as powerful as all of the many variations of the Principle of Mathematical Induction. Namely, if $P(n)$ can be proved for all $n \in \natural^+$ by using any one of the many forms of Mathematical Induction, then it can also be proved by applying \cref{NisWO} to the set
	$$ S = \{\, n \in \natural^+ \mid \enot P(n) \,\} .$$

More precisely, suppose $P(n)$ is not true for all $n \in \natural^+$. Then the fact that $\natural$~is well-ordered tells us that there is a \emph{smallest}~$n$, such that $P(n)$ is not true. This means that:
	\begin{enumerate} \renewcommand{\theenumi}{\roman{enumi}}
	\item $P(n)$ is not true,
	but
	\item $P(k)$ is true for all $k < n$ (such that $k \in \natural^+$).
	\end{enumerate}
Obtaining a contradiction from these two assumptions will complete the proof that $P(n)$ is true for all $n \in \natural^+$.

\begin{eg}[(Alternate proof of \cref{Fn<2nEg})]
Suppose it is not true that $F_n < 2^n$ for all $n \in \natural^+$. (This will lead to a contradiction.) Then, since $\natural$~is well-ordered, there is a smallest~$n$, such that $F_n \ge 2^n$. This means that
	\begin{enumerate} \renewcommand{\theenumi}{\roman{enumi}}
	\item \label{WOFn<2nEgPf-n}
	$F_n \ge 2^n$,
	but
	\item \label{WOFn<2nEgPf-<n}
	$F_k < 2^k$ for all $k < n$ (such that $k \in \natural^+$).
	\end{enumerate}
Note that, since
 	$$ \text{$F_1 = 1 < 2 = 2^1$ \quad and \quad $F_2 =1 < 4 = 2^2$} ,$$
we see from \pref{WOFn<2nEgPf-n} that $n \notin \{1,2\}$, so $n \ge 3$. Therefore  $n-1 \in \natural^+$ and $n-2 \in \natural^+$. Then, since $n - 1$ and $n - 2$ are less than~$n$, we see from \pref{WOFn<2nEgPf-<n} that
	\begin{align} \label{Fn<2nAlt-Less} \tag{$*$}
	\text{$F_{n-1} < 2^{n-1}$ \ and \ $F_{n-2} < 2^{n-2}$.} 
	\end{align}
 Now, we have
 	\begin{align*} F_n 
	&= F_{n-1} + F_{n-2} && \text{(definition of Fibonacci sequence)}
	\\&< 2^{n-1} + 2^{n-2} && \text{(\pref{Fn<2nAlt-Less}: the minimality of~$n$)}
	\\&< 2^{n-1} + 2^{n-1} && (n-2 < n - 1)
	\\&= 2^n
	. \end{align*}
This contradicts \pref{WOFn<2nEgPf-n}.
\def\egSymbol{\proofSymbol} % want end-of-proof symbol !!!
\end{eg}

 \begin{exers} \ \label{OtherInductEx} 
 \begin{problist}
\item \label{OtherInductEx-F(n+4)+Fn} 
 Prove $F_{n + 4} + F_n = 3 F_{n+2}$ for all $n \in \natural^+$.
\item \label{OtherInductEx-2n>n2} 
Prove $2^n > n^2$ for every $n \ge 5$.
\item  \label{OtherInductEx-3n>2n+2n} 
Prove $3^n > 2^n + 2n$, for every $n \ge 2$.
\end{problist}
\end{exers}

\begin{exer} \label{PMI<>WOP} \ 
\begin{problist}
\item \label{PMI<>WOP-ProvePMI}
Show that the Principle of Mathematical Induction \pref{InductionP(n)} follows from the fact that $\natural$~is well-ordered.
%\hint{Let $S = \{\, n \in \natural^+ \mid \enot P(n) \,\}$.}
\item \label{PMI<>WOP-ProveWOP}
Use induction to prove \cref{NisWO}.
\hint{Define $P(n)$ to be the assertion ``If $S \subset \natural$ and $S$ contains an element $\le n$, then $S$ has a smallest element\rlap.''}
\end{problist}
\end{exer}





%\section{Other proofs by induction}
%
%%\begin{defn}
%%Suppose $A_1,A_2,\ldots,A_n$ are sets. Then
%%	$$ \bigcup_{i=1}^n A_i = \bigl\{\, x \mid \exists i \in \{1,2,\ldots,n\}, x \in A_i \,\bigr\} .$$
%%\end{defn}
%%
%%\begin{exer} \label{InductUnionEx}
%%Suppose $A_1,A_2,\ldots,A_n$ are sets. 
%%\begin{enumerate}
%%\item Show $\bigcup_{i=1}^1 A_i = A_1$.
%%\item If $n > 1$, show $\bigcup_{i=1}^n A_i = \left( \bigcup_{i=1}^{n-1} A_i  \right) \cup A_n$.
%%\item Show $ \bigcup_{i=1}^n A_i = A_1 \cup A_2 \cup \cdots \cup A_n$.
%%\end{enumerate}
%%\end{exer}
%






\section{Applications in Number Theory} \label{NumThyInduction}

Induction (or the fact that $\natural$~is well-ordered) can be used to prove many important properties of natural numbers. Here are just three examples.

\begin{defn}
An element~$p$ of~$\natural^+$ is \define[prime number]{prime} iff $p > 1$ and $p$ is not divisible by any element of~$\natural^+$ other than~$1$ and~$p$.
\end{defn}

\begin{prop} \label{HasPrimeFactor}
If $n \in \natural$ and $n > 1$, then $n$~is divisible by a prime number.
\end{prop}

\begin{proof}
Suppose there is some natural number $n > 1$, such that $n$~is not divisible by a prime number. (This will lead to a contradiction.) Since $\natural$~is well-ordered, we may assume that $n$~is the smallest such number, so:
	$$ \text{If $1 < k < n$ (and $k \in \natural$), then $k$~is divisible by a prime number} .$$

Since $n \mid n$, but (by assumption) $n$~is not divisible by any prime number, we know that $n$~is not prime. By definition, this means there exists $k \in \natural$, such that $k \mid n$ and $1 < k < n$. From the minimality of~$n$, we know that $k$~is divisible by some prime number~$p$. Then $p \mid k$ and $k \mid n$, so $p \mid n$. This contradicts the fact that $n$~is not divisible by a prime number.
\end{proof}
%\begin{proof}
%Let 
%	$$S = \{\, k \in \natural \mid \text{$k > 1$ and $k$ is a divisor of~$n$} \,\} .$$
%Since $n \divides n$ \fullsee{DividesPropsEx}{reflexive}, we know $n \in S$, so $S \neq \emptyset$. Therefore, by the Well-Ordering Principle, we may let $a$ be the smallest element of~$S$. Since  $a \in S$, we know $a \mid n$, so it suffices to show that $a$ is prime; we prove this by contradiction.
%
%Suppose $a$ is not prime. Then there is some $d \in \natural^+$, such that
%	$$ \text{$d \divides a$ and $d \notin \{1,a\}$.} $$
%Then $d \divides a$ and $a \divides n$, so $d \divides n$ \fullsee{DividesPropsEx}{transitive}.  We also know $d > 1$. Therefore $d \in S$. Since $a$ is the \emph{smallest} element of~$S$, this implies $d \ge a$. 
%On the other hand, since $d \divides a$, we also know that $d \le a$ (see \fullcref{DividesExers}{less}). Therefore $d = a$, which contradicts the fact that $d \notin \{1,a\}$.
%\end{proof}

\begin{thm}[(\define{Fundamental Theorem of Arithmetic})]
Every natural number \textup(other than $0$ and~$1$\textup) is a product of prime numbers \textup(or is itself a prime\textup).
\end{thm}

\begin{proof}[Proof by contradiction]
Suppose there is some natural number $n > 1$, such that $n$~is not a product of prime numbers (and is not a prime). Since $\natural$~is well-ordered, we may assume that $n$~is the smallest such number, so:
	$$ \text{If $1 < k < n$ (and $k \in \natural$), then $k$~is a product of prime numbers} .$$

Since $n$~is not prime, it is divisible by some natural number~$k$, with $1 < k < n$. This means we may write $n = km$, for some $m \in \natural^+$. Since $m = n/k$ and $1 < k < n$, we see that $1 < m < n$. Therefore, the minimality of~$n$ implies that $k$ and~$m$ are products of prime numbers: say $k = p_1 p_2 \cdots p_r$ and $m = q_1 q_2 \cdots q_s$. Then
	$$ n = km = (p_1 p_2 \cdots p_r)(q_1 q_2 \cdots q_s) $$
is a product of prime numbers. This is a contradiction.
\end{proof}

\begin{rem}
In fact, every natural number can be written in only one way as a product of prime numbers (up to rearranging the order of the factors), but we will not prove this fact.
\end{rem}


\begin{defn}
Let $a,b \in \natural^+$. We say $a$ and~$b$ are \define{relatively prime} iff they have no divisors in common, other than~$1$. (I.e., if $k \in  \natural^+$, and $k$ is a divisor of both $a$ and~$b$, then $k = 1$. In other words, the ``\index{greatest common divisor}greatest common divisor'' of $a$ and~$b$ is~$1$.)
\end{defn}

\begin{thm} \label{GCDLinComb}
Let $a,b \in \natural^+$. If $a$ and~$b$ are relatively prime, then there exist $m,n \in \integer$, such that $ma + nb = 1$.
\end{thm}

\begin{proof}
Let
	$$ S = \{\, ma + nb \mid m,n \in \integer\ k =  \,\} \cap \natural^+. $$
It is easy to see that $a \in S$ (by letting $m = 1$ and $n = 0$), so $S \neq \emptyset$. Therefore, since $\natural$ is well-ordered, we may let $d$ be the smallest element of~$S$.
Then $d \in S$, so we have $d = m_0 a + n_0 b$ for some $m_0,n_0 \in \integer$.

By the Division Algorithm \pref{DivAlgThm}, we may write 
	$$ \text{$a = qd + r$ with $0 \le r < d$} .$$
So
	$$ r = a - qd = a - q(m_0a+n_0b) = (1-qm_0)a + qn_0b = m a + n b ,$$
where $m = 1 - qm \in \integer$ and $n = qn \in \integer$.
On the other hand, since $r < d$, and $d$~is the smallest element of~$S$, we know $r \notin S$. 
 From the definition of~$S$, we conclude that $r = 0$. So $d \divides a$.

By repeating the same argument with $a$ and~$b$ interchanged (and $m_0$ and~$n_0$ also interchanged) we see that $d \divides b$. 

Therefore, $d$ is a divisor of both~$a$ and~$b$. Since $a$ and~$b$ are relatively prime, we conclude that $d = 1$. Since $d \in S$, this means $1 \in S$, which establishes the desired conclusion.
\end{proof}

\begin{exer} \label{ConverseOfGCDLinCombEx}
 Prove the converse of \cref{GCDLinComb}.
\end{exer}

\Cref{GCDLinComb} is of fundamental importance in \define{Number Theory}, the mathematical study of properties of~$\natural$ and~$\integer$. Here are a few of its many consequences:

\begin{exers} \label{LinCombApplsEx}
Assume $a,b \in \natural^+$.
	\begin{problist}
	\item  \label{LinCombApplsEx-xa=1}
	Show $a$ and~$b$ are relatively prime iff there exists $x \in \integer$, such that $xa \equiv 1 \pmod{b}$.
	\item  \label{LinCombApplsEx-xa=y}
	Show $a$ and~$b$ are relatively prime iff for all $y \in \integer$, there exists $x \in \integer$, such that $xa \equiv y \pmod{b}$.
	\item  \label{LinCombApplsEx-CRT}
	(\define{Chinese Remainder Theorem})
	Suppose $a$ and~$b$ are relatively prime. For all $y_1,y_2 \in \integer$, show there exists $x \in \integer$, such that $x \equiv y_1 \pmod{a}$ and $x \equiv y_2 \pmod{b}$.
	\end{problist}
\end{exers}

\Cref{HasPrimeFactor} also has important consequences. For example:

\begin{cor}
There are infinitely many prime numbers.
\end{cor}

\begin{proof}[Proof by contradiction]
Suppose there are only finitely many prime numbers. Then we can make a list of all of them: 
	$$ \text{The set of all prime numbers is $\{p_1,p_2,\ldots,p_n\}$.} $$
Let 
	$$ N = p_1p_2 \cdots p_n .$$
From \cref{HasPrimeFactor}, we know there is some prime~$p$, such that $p \divides (N+1)$. 

Since $p_1,p_2,\ldots,p_n$ is a list of all the prime numbers, we know $p = p_i$, for some~$i$. Therefore $p = p_i$ is one of the factors in the product that defines~$N$, so $p \divides N$. Therefore, $p$ divides both $N$ and~$N+1$, so (from \fullref{DivisorPfEx}{difference}) we have
	$$ p \divides \ \bigl( (N+1) - N\bigr) \ = \ 1 .$$
This implies $p = \pm 1$ (see page~\pageref{NotDiv1}), which contradicts the fact that~$p$, being a prime number, must be $> 1$.
\end{proof}




\begin{summary}
\item Important definitions:
\begin{itemize}
\item proof by induction
\item base case, induction step
\item induction hypothesis
\item relatively prime
\end{itemize}
\item Whenever you need to prove a statement with an $n$ in it, you should consider using induction.
%\item Proof by induction is a special kind of proof that allows us to prove facts about all positive natural numbers.
\item Sequences of numbers are sometimes defined ``recursively\rlap,'' which means that the value of a term may depend on previous terms.
\item There are several alternate forms of induction, including strong induction, generalized induction, and strong induction with multiple base cases.
\item $\natural$ is well-ordered.
\item If $a$ and~$b$ are relatively prime, then $ma + nb = 1$, for some $m,n \in \integer$.
\item Notation:
\begin{itemize}
\item $\sum\limits_{k=1}^n a_k = a_1+a_2 +\cdots +a_n$.
%\item $F_n$ is the $n$th term of the Fibonacci sequence.
\end{itemize}
\end{summary}
