principle of finite inductionPrincipleOfFiniteInduction2001-10-16 08:43:172008-02-27 18:23:30Theoreminduction hypothesisinductive hypothesisbase casebase step\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xypic}\PMlinkescapeword{moment's}
\PMlinkescapeword{complete}
\PMlinkescapeword{equivalent}
\PMlinkescapeword{term}
\PMlinkescapeword{base}
\PMlinkescapeword{hypothesis}
\PMlinkescapeword{range}
The principle of finite induction, also known as \emph{mathematical induction}, is commonly formulated in two ways. Both are equivalent. The first formulation is known as \emph{weak} induction. It asserts that if a statement $P(n)$ holds for $n=0$ and if $P(n)\Rightarrow P(n+1)$, then $P(n)$ holds for all natural numbers $n$. The case $n=0$ is called the \emph{base case} or \emph{base step} and the implication $P(n)\Rightarrow P(n+1)$ is called the \emph{inductive step}. In an inductive proof, one uses the term \emph{induction hypothesis} or \emph{inductive hypothesis} to refer back to the statement $P(n)$ when one is trying to prove $P(n+1)$ from it.
The second formulation is known as \emph{strong} or \emph{complete} induction. It asserts that if the implication $\forall n((\forall m < n P(m))\Rightarrow P(n))$ is true, then $P(n)$ is true for all natural numbers $n$. (Here, the quantifiers range over all natural numbers.) As we have formulated it, strong induction does not require a separate base case. Note that the implication $\forall n((\forall m < n P(m))\Rightarrow P(n)$ already entails $P(0)$ since the statement $\forall m<0 P(m)$ holds vacuously (there are no natural numbers less that zero).
A moment's thought will show that the first formulation (weak induction) is equivalent to the following:
\begin{quote}
Let $S$ be a set natural numbers such that
\begin{enumerate}
\item $0$ belongs to $S$, and
\item if $n$ belongs to $S$, so does $n+1$.
\end{enumerate}
Then $S$ is the set of all natural numbers.
\end{quote}
Similarly, strong induction can be stated:
\begin{quote}
If $S$ is a set of natural numbers such that $n$ belongs to $S$ whenever all numbers less than $n$ belong to $S$, then $S$ is the set of all natural numbers.
\end{quote}
The principle of finite induction can be derived from the fact that every nonempty set of natural numbers has a smallest element. This fact is known as the \emph{well-ordering principle for natural numbers}. (Note that this is not the same thing as the \emph{well-ordering principle}, which is equivalent to the axiom of choice and has nothing to do with induction.)