Second 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({n_0}\right) \land P \left({n_0 + 1}\right) \land \ldots \land P \left({k-1}\right) \land 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, like that of the (first) Principle of Mathematical Induction, 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({n_0}\right) \land P \left({n_0 + 1}\right) \land \ldots \land P \left({k-1}\right) \land 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 the truth of $P \left({k+1}\right)$ follows from the assumption of truth of $P$ for all smaller values of $n$ is called the induction step (also sometimes called the inductive step).

Proof

Follows directly from the Second Principle of Finite Induction.

$\blacksquare$

Comment

Note the difference between this and the (first) Principle of Mathematical Induction, which can be used when it is possible to prove $P \left({k+1}\right)$ directly from the truth of $P \left({k}\right)$.

This principle is often referred to as the Principle of Strong Induction or the Principle of Complete Induction.

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

Sources

• W.E. Deskins: Abstract Algebra (1964): $\S 2.3$: Theorem $2.18$
• Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (1968): $\S 1.2.1$
• C.R.J. Clapham: Introduction to Abstract Algebra (1969)... (previous)... (next): $\S 3.9$: Theorem $15$
• Gary Chartrand: Introductory Graph Theory (1977): Appendix $\text{A}.6$: Theorem $\text{A}.8$