Induction

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

 keyword: tutorial, induction, strong induction, weak 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 standard definitions of the natural numbers. A common one is defining them as the positive integers: {1, 2, 3, 4, ...} and so on.

For the purposes of this article, however, I'd like to introduce a new, equivalent definition of the natural numbers. Consider a set of numbers, S, that follows the following two axioms:

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 $

An equivalent definition of the natural numbers is that it is the smallest set S that follows the two axioms given above.

For the readers familiar with mathematical induction, one may notice that these two axioms are the two things that need to be proven in a proof by induction.

Mathematical Induction

Now that we have the natural numbers defined in a convenient package, let us continue to mathematical induction.

Let f(k) be a statement that is either true or false, and let S be the set of all k for which it is true. By the above construction of the natural numbers, we can see that if S follows the two axioms described above, S must contain the natural numbers.

Example

On first sight, the above definition may be a little hard to grasp and use, so let us consider an example:

Let A be a set or order n. Show that the number of subsets of A is $ 2^n $

Proof by induction:

Before we begin, let's 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 $ mathcal{P}(A) $. It is also often denoted as $ 2^A $, but as we have yet to prove that its order is $ 2^{|A|} $, that should probably be avoided.

Using the above terms, we can rephrase our example into proving the following:

$ |mathcal{P}(A)| = 2^{|A|} $

Now that we have definitions and terms out of the way, let us begin induction:

Let S be the set of numbers k such that $ |mathcal{P}(A)| = 2^{|A|} $, where |A| = k.

Let us begin by proving that the first axiom holds on S:

Consider a set of order 1:

$ A = \{a\} $

We know that therefore:

$ mathcal{P}(A) = \{\{a\}, \{\}\} $

or alternatively:

$ mathcal{P}(A) = \{A, /varnothing\} $

the two trivial subsets.

Therefore, we have that $ |mathcal{A}(S)| = 2^{|A|} $.

Therefore, the first axiom holds.

Next, we wish to show that the second axiom also holds on S:

Suppose we know that k is in S. Prove that k + 1 is also in S.

Let $ A $ be a set of order k.

are such that:

$ mathcal{P}(A) = 2^{|A|} $

We need to show that $ |mathcal{P}(A \cup b)| = 2^{|A| + 1} = 2^{|A \cut b|} $, where b is some element not in A.

The common notation for the set of subsets of a set A is $ 2^A $.

Therefore, what we wish to

Let S be the numbers for which the following statement is true:

Let A be a set of order k. The number of subsets of A is $ 2^k $

To begin, let us consider a set of order 1, let's say

$ A_1 = \{a\} $

This set has two subsets:

$ \{a\}, \{ \} $

Or alternatively:

$ A_1, /varnothing $

Which the reader may recognize as the two trivial subsets.

Therefore, we have that S contains 1, as the set with one element has $ 2^1 $ elements.

Now, let us suppose that S contains k. We wish to show that S also contains k + 1.

We know that the fact that S contains k means that