# Second Principle of Mathematical Induction

## Contents

## 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

- 1966: Richard A. Dean:
*Elements of Abstract Algebra*... (previous) ... (next): $\S 0.1$ - 1977: Gary Chartrand:
*Introductory Graph Theory*... (previous) ... (next): Appendix $\text{A}.6$: Mathematical Induction: Theorem $\text{A}.8$