# Principle of Mathematical Induction

## Contents

## Theorem

Let $P \left({n}\right)$ be a propositional function depending on $n \in \N$.

If the following statements hold:

- $(1): \quad P \left({n_0}\right)$ is true for some $n_0 \in \N$ (where $n_0$ is often, but not always, zero or one)
- $(2): \quad \forall k \in \N: k \ge n_0 : P \left({k}\right) \implies P \left({k+1}\right)$

then $P \left({n}\right)$ is true for all $n \ge n_0$.

This process is called **proof by (mathematical) induction**.

### Basis for the Induction

The step that shows that the proposition is true for the first value $n_0$ is called the **basis for the induction** (also sometimes informally called the **base case**).

### Induction Hypothesis

The assumption made that $P \left({k}\right)$ is true for some $k \in \N$ is the **induction hypothesis** (also sometimes called the **inductive hypothesis**).

### Induction Step

The step which shows that $P \left({k}\right) \implies P \left({k+1}\right)$ is called the **induction step** (also sometimes called the **inductive step**).

## Proof

Suppose that the two given conditions hold:

- $(1): \quad P \left({n_0}\right)$ is true for some $n_0 \in \N$
- $(2): \quad \forall k \in \N: k \ge n_0 : P \left({k}\right) \implies P \left({k+1}\right)$

Let $S = \left\{{x \in \N: P \left({x}\right)}\right\}$.

That is, the set of all $x \in \N$ for which $P \left({x}\right)$ holds.

From Subset of Set with Propositional Function, $S \subseteq \N$.

We have that $n_0 \in S$ from $(1)$.

Now suppose $k \in S$.

That is, $P \left({k}\right)$ holds.

From $(2)$ it follows that $P \left({k + 1}\right)$ holds, and so $k + 1 \in S$.

Thus we have established:

- $S \subseteq \N$
- $n_0 \in S$
- $k \in S \implies k + 1 \in S$

From the Principle of Finite Induction it follows that $\N \setminus \N_{n_0} \subseteq S$.

That is, for every element $k$ of $\N \setminus \N_{n_0}$, it follows that $P \left({k}\right)$ holds.

But $\N \setminus \N_{n_0}$ is precisely the set of all $n \in \N$ such that $n \ge n_0$.

Hence the result.

$\blacksquare$

## Minimal Infinite Successor Set

In the language of the minimal infinite successor set, this principle can be written as:

If:

- $(1): \quad P \left({n_0}\right)$ is true for some $n_0 \in \omega$ (where $n_0$ is often, but not always, zero or one)
- $(2): \quad \forall k \in \omega: k \ge n_0 : P \left({k}\right) \implies P \left({k^+}\right)$

then $P \left({n}\right)$ is true for all $n \ge n_0$.

Here, $k^+$ denotes the successor of $k$, and $\omega$ denotes the minimal infinite successor set.

## Natural Numbers in Real Numbers

If the natural numbers $\N$ are considered part of the real numbers $\R$, this principle can be written as:

If $A \subseteq \N$ is an inductive set, then $A = \N$.

## Also known as

This principle is sometimes referred to as the **Principle of Weak Induction**.

Other sources use the term **First Principle of Mathematical Induction**.

## Also see

Note the difference between this and the Second Principle of Mathematical Induction, which can often be used when it is not possible to prove $P \left({k+1}\right)$ *directly* from the truth of $P \left({k}\right)$, but when it *is* possible to prove $P \left({k+1}\right)$ from the assumption of the truth of $P \left({n}\right)$ for *all* values of $n_0$ such that $n_0 \le n \le k$.

In Equivalence of Well-Ordering Principle and Induction it is proved that this, the Second Principle of Mathematical Induction and the Well-Ordering Principle are all logically equivalent to each other.

## Sources

- W.E. Deskins:
*Abstract Algebra*(1964)... (previous)... (next): $\S 2.1$: Theorem $2.1$ - Richard A. Dean:
*Elements of Abstract Algebra*(1966)... (previous)... (next): $\S 0.1$: Theorem $4$ - C.R.J. Clapham:
*Introduction to Abstract Algebra*(1969)... (previous)... (next): $\S 3.9$: Theorem $14$ - George E. Andrews:
*Number Theory*(1971)... (previous)... (next): $\S 1.1$ - A. G. Howson:
*A Handbook of Terms used in Algebra and Analysis*(1972)... (previous)... (next): $\S 4$: Number systems I: Peano's Axioms - K.G. Binmore:
*Mathematical Analysis: A Straightforward Approach*(1977)... (previous)... (next): $\S 3.8$ - Gary Chartrand:
*Introductory Graph Theory*(1977)... (previous)... (next): Appendix $\text{A}.6$: Mathematical Induction: Theorem $\text{A}.7$ - P.M. Cohn:
*Algebra Volume 1*(2nd ed., 1982)... (previous)... (next): $\S 2.1$: The integers: $\mathbf{I}$ - H. Jerome Keisler and Joel Robbin:
*Mathematical Logic and Computability*(1996)... (previous)... (next): Appendix $\text{A}.12$: Induction - Michael R.A. Huth and Mark D. Ryan:
*Logic in Computer Science: Modelling and reasoning about systems*(2000)... (previous)... (next): $\S 1.4.2$: Mathematical induction: Definition $1.29$ - James R. Munkres:
*Topology*(2nd ed., 2000)... (previous)... (next): $1$: Set Theory and Logic: $\S 4$: The Integers and the Real Numbers - Paul Halmos and Steven Givant:
*Introduction to Boolean Algebras*(2008)... (previous)... (next): Appendix $\text{A}$: Set Theory: Induction - M. Ben-Ari:
*Mathematical Logic for Computer Science*(3rd ed., 2012)... (previous): Appendix $\text{A}.6$

- For a video presentation of the contents of this page, visit the Khan Academy.