Skip to main content

Section 1.14 A first look at induction

Recall that we defined the natural numbers as sets in an iterative fashion. We declare zero to be \(0 = \varnothing\text{,}\) and if \(n\) is a natural number, then its successor is the set \(n + 1 = S(n) = n\cup\{n\}\text{.}\)

Then the set of all natural numbers

\begin{equation*} \NN_0 = \{ 0, 1, 2, \dots \} \end{equation*}

is characterized in the following way. A set \(M\) is said to be successive if and only if \(0\in M\text{,}\) and for any \(A \in M\text{,}\) one has \(S(A)\in M\text{.}\) Now \(\NN_0\) is defined to be the smallest successive set; that is, \(\NN_0\) is the successive set such that no proper subset \(T \subset \NN_0\) is successive.

One fanstatic consequence of this definition is that it embodies the Principle of Mathematical Induction. Here's how that works. Let's say you've got a statement \(\phi(n)\) with a free variable \(n\text{,}\) and let's say that you suspect it's true for all natural numbers \(n\text{.}\) If you can prove \(\phi(0)\) as well as \((\forall m \in \NN_0)(\phi(m) \Longrightarrow \phi(m+1))\text{,}\) then you can conclude that every natural number has the property \(\phi\text{.}\)

Why is this true? Well, consider the set \(X = \{n\in \NN_0 : \phi(n)\}\) of all those natural numbers with property \(\phi\text{.}\) If you prove that \(\phi(0)\text{,}\) then you'll have shown that \(0\in X\text{.}\) If you prove that \((\forall m \in \NN_0)(\phi(m) \Longrightarrow \phi(m+1)\) as well, then you'll have shown that \(X\) is a successive set. But since no proper subset of \(\NN_0\) is successive, it follows that \(X=\NN_0\text{.}\) That means that for every natural number \(n\text{,}\) we have \(\phi(n)\text{.}\)

Why is this helpful? Induction gives us footholds for working our way up the tower of natural numbers. It is usually not so difficult to check \(\phi(0)\) by hand; this is sometimes called the base case for the induction. Then one wants to prove that, for every \(n\in\NN_0\text{,}\) the statement \(\phi(m)\) implies the statement \(\phi(m+1)\text{.}\) For this, one is allowed to assume \(\phi(m)\) (the induction hypothesis and to try to deduce \(\phi(m+1)\text{.}\)

Let us prove by induction that for any natural number \(n\text{,}\) one has

\begin{equation*} 0+1+2+\cdots+n = \frac{n(n+1)}{2}\text{.} \end{equation*}

When \(n=0\text{,}\) this is the claim that \(0 = \frac{0\cdot 1}{2}\text{,}\) which is certainly true. Now let \(m\in\NN_0\text{,}\) and assume that

\begin{equation*} 0+1+2+\cdots+m = \frac{m(m+1)}{2}\text{.} \end{equation*}

From this we deduce

\begin{equation*} 0+1+2+\cdots+m+(m+1) = \frac{m(m+1)}{2}+m+1 = \frac{m(m+1)}{2}+\frac{2(m+1)}{2} = \frac{(m+1)(m+2)}{2}\text{.} \end{equation*}

Thus by the Principle of Mathematical Induction, we deduce that for any natural number \(n\text{,}\) one has

\begin{equation*} 0+1+2+\cdots+n = \frac{n(n+1)}{2}\text{.} \end{equation*}

We will see many more examples, along with an elaboration of induction techniques, later in the course.