Induction

by: Robert Hansen, proud member of the math squad.

 keyword: tutorial, induction 

The Natural Numbers

Before we can talk about induction, we must first talk about the natural numbers, and their properties.

I'm certain the reader is familiar with the natural numbers. A common one way of defining them as the positive integers: {1, 2, 3, 4, ...}.

For the purposes of induction, however, it is much more convenient to define them in a different way.

Consider the following two statements about a set S:

(1) 1 is contained in S

(2) if k is in S, then k + 1 is also in S

In more mathematical notation, we have:

$ 1\in S $

$ k \in S \Rightarrow k + 1 \in S $

Definition (alternate): The natural numbers are the smallest set that satisfy both (1) and (2).

Here, what smallest means is that if A is a set that satisfies (1) and (2), then $ N \subset A $.

We can see this intuitively. The elements of the natural numbers are {1, 1 + 1, 1 + 1 + 1, ...} and can be defined recursively by defining each element as one plus the element before it. Therefore, if a set were to contain 1, and follow property (2), then the natural numbers must be contained within it.

Mathematical Induction

To formalize it, let us state what we stated above as a theorem:

Theorem (Induction Principle): Let S be a set of numbers. If S satisfies (1) and (2), then S must contain the natural numbers.

This is mathematical induction.

However, as it may not be immediately clear why, let us consider an example.

Example

Proposition: Let A be a set. The number of subsets of A is $ 2^{\|A\|} $

Before we begin trying to prove this with the induction principle stated above, let us first define some terms. The set of the subsets of a set A is called the power set of A, and can be denoted as $ P(A) $.

Using this new terminology and notation, the above proposition can be rewritten in the following way:

Proposition: Let A be a set. $ \|P(A)\| = 2 ^ {\|A\|} $

To prove that this is true for all natural numbers, let S be the set of k for which the above holds, where k is the order of the set A.

Keep in mind that since we are only working with sets in this proposition, we needn't worry about different sets of the same order. They're all going to have the same number of subsets.

The first thing to notice about this proposition is that it is true for a set of order 1. Such a set has only two subsets: the whole set and the empty set. Because $ 2 = 2^1 $ (clearly), the proposition must hold.

Therefore, 1 is contained in S.

The next thing we'd like to notice is that if we have two sets A and A', where the only difference between the two is that A' has one extra element a', which is not in A, then the number of subsets of A' we should be able to divide into two groups: subsets of A' which contain a' and subsets of A' which do not.

The subsets of A' that do not contain a' must simply be the subsets of A, and those that do are simply the subsets of A union a'. Therefore, we have that $ \|P(A')\| = 2*\|P(A)\| $.

From this, we see that S satisfies property (2). Therefore, by the induction principle S must hold for all natural numbers, and therefore our proposition holds for all natural numbers.

The last thing to check is the empty set, which has order 0, but it can be easily shown that its power set is the empty set (a single element), and therefore our proposition holds for all sets.

Conclusion

Although the above is simply another way to look at the idea of mathematical induction, I've found that it has helped me quite a bit in intuitively comprehending the concepts behind mathematical induction.