The Principle of Mathematical Induction

We now present a valuable tool for proving results about integers. This tool is the principle of mathematical induction .

Theorem 1. The First Principle of Mathematical Induction

If a set of positive integers has the property that, if it contains the integer $k$, then it also contains $k + 1$, and if this set contains 1 then it must be the set of all positive integers. More generally, a property concerning the positive integers that is true for $n = 1$, and that is true for the integer $n + 1$  whenever it is true for the integer n, must be true for all positive integers. We use the well ordering principle to prove the first principle of mathematical induction.

Proof. Let $S$ be the set of positive integers containing the integer 1, and the integer $k + 1$ whenever it contains k. Assume also that $S$ is not the set of all positive integers. As a result, there are some integers that are not contained in $S$ and thus those integers must have a least element $x$ by the well ordering principle. Notice hat $x = 1$ since 1 in S. But $x - 1$ in $S$ and thus using the property of $S$, $x$ in $S$. Thus $S$ must contain all positive integers.

Theorem 2. The Second Principle of Mathematical Induction

A set of positive integers that has the property that for every integer $k$, if it contains all the integers 1 through k then it contains $k + 1$ and if it contains 1 then it must be the set of all positive integers. More generally, a property concerning the positive integers that is true for $n = 1$, and that is true for all integers up to $n + 1$ whenever it is true for all integers up to n, must be true for all positive integers.

The second principle of induction is also known as the principle of strong induction. Also, the first principle of induction is known as the principle of weak induction. To prove the second principle of induction, we use the first principle of induction.

Proof. Let T be a set of integers containing 1 and such that for every positive integer k, if it contains 1, 2, ..., k, then it contains k + 1. Let S be the set of all positive integers k such that all the positive integers less than or equal to k are in T . Then 1 is in S, and we also see that k + 1 is in S. Thus S must be the set of all positive integers. Thus T must be the set of all positive integers since S is a subset of T .

Share :