A first look at induction

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 = \emptyset,

and if

n

is a natural number, then its successor is the set

n + 1 = S (n) = n \cup {n} .

🔗

Then the set of all natural numbers

N_{0} = {0, 1, 2, \dots}

🔗

is characterized in the following way. A set

M

is said to be successive if and only if

0 \in M,

and for any

A \in M,

one has

S (A) \in M .

Now

N_{0}

is defined to be the smallest successive set; that is,

N_{0}

is the successive set such that no proper subset

T \subset N_{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

φ (n)

with a free variable

n,

and let's say that you suspect it's true for all natural numbers

n .

If you can prove

φ (0)

as well as

(\forall m \in N_{0}) (φ (m) ⟹ φ (m + 1)),

then you can conclude that every natural number has the property

φ .

🔗

Why is this true? Well, consider the set

X = {n \in N_{0} : φ (n)}

of all those natural numbers with property

φ .

If you prove that

φ (0),

then you'll have shown that

0 \in X .

If you prove that

(\forall m \in N_{0}) (φ (m) ⟹ φ (m + 1)

as well, then you'll have shown that

X

is a successive set. But since no proper subset of

N_{0}

is successive, it follows that

X = N_{0} .

That means that for every natural number

n,

we have

φ (n) .

🔗

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

φ (0)

by hand; this is sometimes called the base case for the induction. Then one wants to prove that, for every

n \in N_{0},

the statement

φ (m)

implies the statement

φ (m + 1) .

For this, one is allowed to assume

φ (m)

(the induction hypothesis and to try to deduce

φ (m + 1) .

🔗

Example 1.14.1. A simple induction argument.

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.