Mathematical Induction

Induction is closely related to recursion. If a base case satisfies a property and a step carries the property from one element to the next, then the property holds for every element reachable from the base case by repeatedly applying the step.

Below is the principle of induction as presented by various authors.

We start with Charles Pinter ¹.

Consider the following conditions:

1. $S_1$ is true.
2. For any $k>0 \in \mathbb{Z}$, if $S_k$ is true, then also $S_{k+1}$ is true.

If conditions 1 and 2 are satisfied, then $S_n$ is true for every positive integer n.

Then, the definition by Halmos ²:

1. $0 \in \omega$
2. if $n\in \omega$, then $n^{+}\in \omega$, where $n^+ = n \cup \{n\}$
3. if $S\subset \omega$, if $0\subset S$, and if $n^+ \in S$, whenever $n\in S$, then $S=\omega$

Finally, Hamkins ³:

Least number principle: if there is a natural number with a property, then there is a smallest number with that property.

Common induction principle: Suppose that $A$ is a set of natural numbers with $0\in A$. Whenever $n\in A$, then also $n+1 \in A$. Therefore, every natural number is in $A$.

The base case (e.g., $S_1$ is true, or $0\in A$), is referred to as the anchor, whereas the implication (e.g., $S_{k+1}$ is true or $n+1 \in A$), is called the induction step.

Examples

The following is an inductive proof, written in Lean, of the fact that:

This is also the method used to calculate the nth triangular number ³:

The following figure makes it easier to visualize the recursion used in the proof:

4th and 5th triangular numbers plotted using figural

Finally, here is an example of an equality that I encountered in seventh grade while reading The Man Who Counted.

According to the legend narrated in this book, after King Iadava insisted, Sessa asked for one grain of wheat for the first cell, two for the second, four for the third, and so on as a reward for inventing the game of chess:

The following Lean code proves that:

References