Principle of Mathematical Induction

Anyone who has had a good grounding in school mathematics must be familiar with two uses of mathematical induction.

1. Definition of functions and relations by mathematical induction,
2. Proofs by the principle of mathematical induction.

We present below some familiar examples of definitions by mathematical induction.

Example 2.1   The factorial function on natural numbers (of the type $f: \mathbb{N}\rightarrow \mathbb{N}$) is defined as follows

Basis.

$0! = 1$

Induction step.

$(n+1)! = (n+1) * n!$

Example 2.2   The $n^{th}$ power (where $n$ is a natural number) of a positive number $x$ is often defined as

Basis.

$x^0 = 1$

Induction step.

$x^{n+1} = x^n * x$

This is a function of the type $f: \mathbb{P}\times \mathbb{N}\rightarrow \mathbb{P}$.

Example 2.3   The set of $n$-tuples of natural numbers can be defined in terms of Cartesian products as

Basis.

$\mathbb{N}^1 = \mathbb{N}$

Induction step.

$\mathbb{N}^{n+1} = \mathbb{N}^n \times \mathbb{N}$

Example 2.4   For binary relations $R$ and $S$ on $A$ we define their composition (denoted $R \circ S$) as follows.

$$R \circ S = \{(a,c) \mid$$   $$\mbox{for some $b \in A$, $(a,b) \in R$\ and $(b,c) \in S$}$$$$\}$$

We may extend this binary relational composition to an $n$-fold composition of a single relation $R$ as follows.

Basis.

$R^1 = R$

Induction step.

$R^{n+1} = R \circ R^n$

Similarly the principle of mathematical induction is the means by which we have often proved (as opposed to defining) properties about numbers, or statements involving the natural numbers. The principle may be stated as follows.

Principle of Mathematical Induction (PMI) - Version 1

A property ${\bf P}$ holds for all natural numbers provided

Basis step:

${\bf P}$ holds for 0, and

Induction step:

If ${\bf P}$ holds for an arbitrary $n \geq 0$, ${\bf P}$ also holds for $n+1$

The underlined portion, called the Induction hypothesis, is an assumption that is necessary for the conclusion to be proved. Intuitively, the principle captures the fact that in order to prove any statement involving natural numbers, it suffices to do it in two steps. The first step is the basis which needs to be proved. The proof of the induction step essentially tells us that the reasoning involved in proving the statement involving the other natural numbers is the same once the basis has been proved. Hence instead of an infinitary proof (one for each natural number) we have a compact finitary proof which exploits the similarity of the proofs for all the naturals except the basis.

Example 2.5   We prove that all natural numbers of the form $n^3 + 2n$ are divisible by 3.

Proof.

Basis.

For $n = 0$, we have $n^3 + 2n = 0$ which is divisible by 3.

Induction hypothesis.

$n^3 + 2n$ is divisible by 3 for an arbitrary $n \geq 0$.

Induction step.

Consider $(n+1)^3 + 2(n+1)$. We have

$$(n+1)^3 + 2(n+1)$$

$$= (n^3 + 3n^2 + 3n + 1) + (2n + 2)$$

$$= (n^3 + 2n) + 3(n^2 + n + 1)$$

which is divisible by 3.

$\qedsymbol$

Several versions of this principle exist. We state some of the most important ones. In each case, the underlined portion is the induction hypothesis. For example it is not necessary to consider 0 (or even 1) as the basis step. Any integer $k$ could be considered the basis, as long as the property is to be proved for all $n \geq k$.

Principle of Mathematical Induction (PMI) - Version 2

A property ${\bf P}$ holds for all natural numbers, $n \geq k \geq 0$ provided

Basis step:

${\bf P}$ holds for $k$, and

Induction step:

If ${\bf P}$ holds for an arbitrary $n \geq k$, then ${\bf P}$ holds for $n+1$.

Such a version seems very useful when the property to be proved is not true or is undefined for 0 or 1. The following example illustrates this.

Example 2.6   Suppose we have stamps of two different denominations, 3 paise and 5 paise. We want to show that it is possible to make up exactly any postage of 8 paise or more using stamps of these two denominations [Liu]. Thus we want to show that every positive integer $n \geq 8$ is expressible as $n = 3i + 5j$ where $i,j \geq 0$.

Proof.

Basis.

For $n = 8$, we have $n = 3 + 5$, i.e. $i = j = 1$.

Induction hypothesis.

$n = 3i + 5j$ for an $n \geq 8$, $i,j \geq 0$.

Induction step.

Consider $n+1$. If $j = 0$ then clearly $i \geq 3$ and we may write $n+1$ as $3(i - 3) + 5(j + 2)$. Otherwise $n+1 = 3(i + 2) + 5(j - 1)$.

$\qedsymbol$

In the next version we strengthen the hypothesis.

Principle of Mathematical Induction (PMI) - Version 3

A property ${\bf P}$ holds for all natural numbers provided

Basis step:

${\bf P}$ holds for 0, and

Induction step:

If ${\bf P}$ holds for all $m$, $0 < m \leq n$ for an arbitrary $n \geq 0$, then ${\bf P}$ also holds for $n+1$.

Example 2.7   Let $F_0 = 0,\; F_1 = 1, \;F_2 = 1, \ldots$ be the Fibonacci sequence where for all $n \geq 2$, $F_n = F_{n-1} + F_{n-2}$. Let $\phi = (1 + \sqrt{5})/2$. We now show that $F_n \leq \phi^{n-1}$ for all positive $n$.

Proof.

Basis.

For $n = 1$, we have $F_1 = \phi^0 = 1$.

Induction hypothesis.

$F_n \leq \phi^{n-1}$ for all $m$, $1 \leq m \leq n$.

Induction step.

$$\begin{array}{llll} F_{n+1} & = & F_n + F_{n-1} \\ & \leq & \phi... ...-2}(\phi + 1) \\ & = & \phi^n & \mbox{(since $\phi^2 = \phi + 1$)} \end{array}$$

$\qedsymbol$

Versions 1 and 2 of PMI rely on the fact that starting from 0 (or $k$) every integer larger than 0 (or $k$) may be obtained by successively adding 1 to the previous one, whereas version 3 is obtained by considering the natural numbers as being totally ordered by the $<$ relation.

Since the natural numbers are themselves defined as the smallest set $\mathbb{N}$ such that $0 \in \mathbb{N}$ and whenever $n \in \mathbb{N}$, $n+1$ also belongs to $\mathbb{N}$. Therefore we may state yet another version of PMI from which the other versions previously stated may be derived. The intuition behind this version is that a property ${\bf P}$ may also be considered as defining a set $S = \{ x \mid x$    satisfies ${\bf P}\}$. Therefore if a property ${\bf P}$ is true for all natural numbers the set defined by the property is the set of natural numbers. This gives us the last version of PMI.

Principle of Mathematical Induction (PMI) - Version 0

For a set $S$, $S = \mathbb{N}$ provided

Basis step:

$0 \in S$, and

Induction step:

If $n \in S$, then $n+1 \in S$.