\documentclass[11pt,twoside]{article}
\usepackage{latexsym}
\newcommand{\docdate}{August 21, 2005}
\newcommand{\doctitle}{Review of Mathematical Induction}
\pagestyle{myheadings}
\markboth{\hfill\doctitle\hfill\docdate}{\docdate\hfill\doctitle\hfill}
\addtolength{\textwidth}{1.00in}
\addtolength{\textheight}{1.00in}
\addtolength{\evensidemargin}{-1.00in}
\addtolength{\oddsidemargin}{-0.00in}
\addtolength{\topmargin}{-.50in}
\setlength{\footskip}{0pt}
\renewcommand{\theenumi}{\textbf{\Alph{enumi}}}
\renewcommand{\theenumii}{\textbf{\roman{enumii}}}
\newcommand{\naturals}{\mathbf{N}}
\newcommand{\property}{\mathbf{P}}
\title{\doctitle}
\author{Lenwood S. Heath}
\date{\docdate}
\begin{document}
\thispagestyle{empty}
\maketitle
\section{Principle of Mathematical Induction}
Let $\property$ be some property of the natural numbers $\naturals$,
the set of non-negative integers.
Alternately,
$\property(n)$ is a statement about a natural number $n\in\naturals$
that is either true or false.
The purpose of induction is to show that $\property(n)$ is true
for all $n\in\naturals$.
Here are three variants of the Principle of Mathematical Induction.
\paragraph{Principle of Mathematical Induction (First Variant).}
Suppose that we can prove these two statements:
\begin{itemize}
\item
\textbf{Base case.}
$\property(0)$ is true.
\item
\textbf{Inductive step.}
If $\property(k)$ is true for any $k\in\naturals$,
then $\property(k+1)$ is also true.
\end{itemize}
Then,
by the Principle of Mathematical Induction,
$\property(n)$ is true for all $n\in\naturals$.
\paragraph{Principle of Mathematical Induction (Second Variant).}
Suppose that $b\in\naturals$
and that we can prove these two statements:
\begin{itemize}
\item
\textbf{Base case.}
$\property(k)$ is true for $0\leq k \leq b$.
\item
\textbf{Inductive step.}
If $\property(k)$ is true for some $k\geq b$,
then $\property(k+1)$ is also true.
\end{itemize}
Then,
by the Principle of Mathematical Induction,
$\property(n)$ is true for all $n\in\naturals$.
\paragraph{Principle of Mathematical Induction
(Third Variant; Strong Induction).}
Suppose that $b\in\naturals$
and that we can prove these two statements:
\begin{itemize}
\item
\textbf{Base case.}
$\property(k)$ is true for $0\leq k \leq b$.
\item
\textbf{Inductive step.}
If $k\geq b$ and $\property(i)$ is true for all $i\leq k$,
then $\property(k+1)$ is also true.
\end{itemize}
Then,
by the Principle of Mathematical Induction,
$\property(n)$ is true for all $n\in\naturals$.
\section{Proof by Induction}
An \textbf{inductive argument} to prove
that a property $\property$ of $\naturals$
is true for all natural numbers
is structured as follows:
\paragraph{Basis.}
Prove $\property(0)$.
\paragraph{Inductive hypothesis.}
Assume that $\property(k)$ is true
for an arbitrary $k\in\naturals$.
\paragraph{Inductive step.}
Prove that the inductive hypothesis
implies $\property(k+1)$.
\bigskip
By the Principle of Mathematical Induction (First Variant),
$\property(n)$ is true for all $n\in\naturals$.
\section{Example of An Inductive Argument}
Prove by induction on $n$ that $n^4-4n^2$ is divisible by 3,
for all $n\geq0$.
\paragraph{Base case:}
If $n = 0$, then $n^4-4n^2 = 0$,
which is divisible by 3.
\paragraph{Inductive hypothesis:}
For some $n\geq0$,
$n^4-4n^2$ is divisible by 3.
\paragraph{Inductive step:}
Assume the inductive hypothesis is true for $n$.
We need to show that $(n + 1)^4 - 4 (n + 1)^2$ is divisible by 3.
By the inductive hypothesis,
we know that $n^4-4n^2$ is divisible by 3.
Hence $(n + 1)^4 - 4 (n + 1)^2$ is divisible by 3
if $(n + 1)^4 - 4 (n + 1)^2 - (n^4-4n^2)$ is divisible by 3.
Now
\begin{eqnarray*}
\lefteqn{(n + 1)^4 - 4 (n + 1)^2 - (n^4-4n^2)} \\
& = & n^4 + 4 n^3 + 6n^2 + 4n +1 - 4 n^2 - 8n -4 -n^4+4n^2 \\
& = &
4 n^3 + 6 n^2 - 4n -3,
\end{eqnarray*}
which is divisible by 3 if $4 n^3 - 4n$ is.
Since $4 n^3 - 4n=4n(n+1)(n-1)$,
we see that $4 n^3 - 4n$ is always divisible by 3.
Going backwards,
we conclude that $(n + 1)^4 - 4 (n + 1)^2$ is divisible by 3,
and that the inductive hypothesis holds for $n+1$.
\bigskip
By the Principle of Mathematical Induction,
$n^4-4n^2$ is divisible by 3,
for all $n\in\naturals$.
\section{Another Example}
Define a set $Y$
with a recursive definition.
\begin{enumerate}
\item
\textbf{Basis:}
$7\in Y$.
\item
\textbf{Recursive step:}
If $y\in Y$,
then $y+21\in Y$ and $y+49\in Y$.
\item
\textbf{Closure:}
The only elements of $Y$ are those obtained
from the basis
and those obtained from the basis by a finite number of applications
of the recursive step.
\end{enumerate}
Prove by induction that every element of $Y$
is divisible by 7.
\paragraph{Base case:}
The base case of the recursive definition is $7\in Y$
and $7$ is divisible by $7$.
Hence the statement is true for the base case.
\paragraph{Inductive hypothesis:}
For some $k\in\naturals$,
every element of $Y$ obtained
by $k$ applications of the recursive step
is divisible by 7.
\paragraph{Inductive step:}
Assume that $k\in\naturals$
and the inductive hypothesis holds for $k$.
Let $y\in Y$ be obtained by $k+1$ applications of the recursive step.
Then,
there exists $y'\in Y$
such that $y'$ is obtained by $k$ applications of the recursive step
and $y$ is obtained from $y'$
by one application of the recursive step.
By the inductive hypothesis,
$y'$ is divisible by 7.
Either $y=y'+21$ or $y=y'+49$;
in either case,
$y$ is divisible by 7,
since $y'$, 21, and 49 are divisible by 7.
Hence,
every element of $Y$ obtained by $k+1$ applications of the recursive step
is divisible by 7.
\bigskip
By the Principle of Mathematical Induction,
every element of $Y$ obtained by a finite number of applications
of the recursive step is divisible by 7;
hence,
all elements of $Y$ are divisible by 7.
\section{Exercise in Proof by Induction}
Here are two definitions of the set of undirected trees.
\paragraph{First Definition of an undirected tree.}
An \textbf{undirected tree}
is an undirected graph
that is connected and that contains no cycle.
\paragraph{Second Definition of an undirected tree.}
The set $Z$ of \textbf{undirected trees}
is defined recursively by
\begin{enumerate}
\item
\textbf{Basis:}
The basis set $Z_0$ consists
of every undirected graph having a single vertex
and no edges.
\item
\textbf{Recursive step:}
If $T$ is a tree,
then the addition of a new vertex $v$ and
an edge from $v$ to any vertex of $T$ results in a tree.
\item
\textbf{Closure:}
The only elements of $Z$ are those in $Z_0$
and those obtained from $Z_0$ by a finite number of applications
of the recursive step.
\end{enumerate}
\paragraph{Exercise:}
Show that the two definitions are equivalent
(define the same set of graphs).
\end{document}