Principle of Mathematical Induction

Theorem

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

If you can show two things:

$(1): \quad$ That $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$ That $\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

Follows directly from the Principle of Finite Induction.

$\blacksquare$

Comment

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$.

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

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

• Nathan Jacobson: Lectures in Abstract Algebra: I. Basic Concepts (1951): Introduction $\S 4$
• Richard A. Dean: Elements of Abstract Algebra (1966): $\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): $\S 1.1$
• K.G. Binmore: Mathematical Analysis: A Straightforward Approach (1977)... (previous)... (next): $\S 3.8$
• Gary Chartrand: Introductory Graph Theory (1977): Appendix $\text{A}.6$: Theorem $\text{A}.7$
• H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): Appendix $\text{A}.12$
• For a video presentation of the contents of this page, visit the Khan Academy.