Second Principle of Mathematical Induction

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\map P n$ be a propositional function depending on $n \in \Z$.

Let $n_0 \in \Z$ be given.


Suppose that:

$(1): \quad \map P {n_0}$ is true
$(2): \quad \forall k \in \Z: k \ge n_0: \map P {n_0} \land \map P {n_0 + 1} \land \ldots \land \map P {k - 1} \land \map P k \implies \map P {k + 1}$


Then:

$\map P n$ is true for all $n \ge n_0$.


This process is called proof by (mathematical) induction.


The second principle of mathematical induction is usually stated and demonstrated for $n_0$ being either $0$ or $1$.

This is often dependent upon whether the analysis of the fundamentals of mathematical logic are zero-based or one-based.


Zero-Based

Let $\map P n$ be a propositional function depending on $n \in \N$.

Suppose that:

$(1): \quad \map P 0$ is true
$(2): \quad \forall k \in \N: \map P 0 \land \map P 1 \land \ldots \land \map P {k - 1} \land \map P k \implies \map P {k + 1}$


Then:

$\map P n$ is true for all $n \in \N$.


One-Based

Let $\map P n$ be a propositional function depending on $n \in \N_{>0}$.

Suppose that:

$(1): \quad \map P 1$ is true
$(2): \quad \forall k \in \N_{>0}: \map P 1 \land \map P 2 \land \ldots \land \map P {k - 1} \land \map P k \implies \map P {k + 1}$


Then:

$\map P n$ is true for all $n \in \N_{>0}$.


Proof

For each $n \ge n_0$, let $\map {P'} n$ be defined as:

$\map {P'} n := \map P {n_0} \land \dots \land \map P n$

It suffices to show that $\map {P'} n$ is true for all $n \ge n_0$.


It is immediate from the assumption $\map P {n_0}$ that $\map {P'} {n_0}$ is true.

Now suppose that $\map {P'} n$ holds.

By $(2)$, this implies that $\map P {n + 1}$ holds as well.

Consequently, $\map {P'} n \land \map P {n + 1} = \map {P'} {n + 1}$ holds.


Thus by the Principle of Mathematical Induction:

$\map {P'} n$ holds for all $n \ge n_0$

as desired.

$\blacksquare$


Also defined as

This principle can often be found stated more informally, inasmuch as the propositional function $P$ is referred to as "a statement about integers".


Terminology

Basis for the Induction

The step that shows that the proposition $\map P {n_0}$ is true for the first value $n_0$ is called the basis for the induction.


Induction Hypothesis

The assumption that $\forall j: n_0 \le j \le k: \map P j$ is true for some $k \in \Z$ is the induction hypothesis.


Induction Step

The step which shows that the truth of $\map P {k + 1}$ follows from the assumption of truth of $P$ for all values of $j$ between $n_0$ and $k$ is called the induction step.


Also known as

The Second Principle of Mathematical Induction is also known as the Principle of Complete Induction.

Both terms are used on $\mathsf{Pr} \infty \mathsf{fWiki}$.

The abbreviation PCI is also used.


Some sources call it the Principle of Strong Induction.

Such sources may similarly refer to the (First) Principle of Mathematical Induction as the Principle of Weak Induction.

These names are misleading, as both principles are equivalent, and so neither is weaker or stronger than the other.


Some sources prefer to call it course-of-values induction, but this is possibly idiosyncratic.


The process of demonstrating a proof by means of the Second Principle of Mathematical Induction is often referred to as Proof by Complete Induction.


Also see

  • Results about Proofs by Induction can be found here.


Sources