« previous section    next section »


8.3  The principle of mathematical induction

The most popular formulation of the mathematical induction principle is based on the fact, that every subset A of an arbitrary set determines some property (characteristics) PT which refers only to this subset's elements. Let PT(n) be the property defined in the set of natural numbers. Then, the principle of induction may be formulated as  in  the following schema:

If

(1) PT(0), i.e. 0 has PT property and

(2) for every natural number n, if PT(n) then PT(n+1),

then for every n,  PT(n) holds (i.e. every natural number has the PT property).

The proofs of mathematical theorems which are derived using the induction principle we name induction proofs.

How to create a correct induction proof? The first step is to show that the natural number 0 has the property PT. This part of proof is usually called the base of induction. Then we assume that for some arbitrary number n, n has PT property, i.e. we assume that P(n) holds. This assumption is called the induction assumption. Using the induction assumption we derive induction thesis, i.e. we prove that property PT holds for the next natural number n+1. This step is called induction step. Finally, we can conclude that the considered property PT holds for all natural numbers (every n ∈ N has PT property).

We will illustrate the idea of induction proof on a few examples.

Lemma 8.3.1

There are exactly 2n subsets of n-element set, i.e. for any set X, 
|X| = n implies |P(X)| = 2n.

Proof.

Let's mark with PT a sentence which describes the following natural number's property

PT(n) if and only if there are exactly 2n subsets of n-element set.

Induction base. Because empty set has exactly one subset thus, if |X|=0 then |P(X)|=1 = 20. This demonstrates that number 0 has PT property.

Induction assumption. Let's assume that all k-element sets have PT property (i.e. the number of all subsets of any k-element set is equal to 2k).

Induction thesis. We are going to prove that every (k+1)-element set has PT property either.

Thesis proof. Let's consider the (k+1)-element set X, X = {x1,x2,..., xk,xk+1}. We split all subsets of X into two disjoint categories:

(*) subsets of set X which do not include the element xk+1,

(**) subsets of set X which include the element xk+1.

Of course, all (*)-type subsets are subsets of the k-element set, thus according to induction assumption, the number of these sets is equal to 2k. In order to build all subsets of type (**) it is enough to take all subsets over the k-element set X\{x k+1} and append to them the element xk+1. Again using the induction assumption we can estimate the number of (**)-type subsets by 2k. Adding up two disjoint cases we obtain 2k + 2k = 2k+1 subsets in total. Therefore, the property PT holds for k+1.

According to the induction principle, we can conclude, that every natural number n has the property PT. ♦

Sometimes it is convenient to apply a bit different version of the induction principle in which the induction assumption is much stronger than the one in Peano's axiom Ax5. We show that this new formulation of the induction principle is a consequence of the Peano's axioms.

Theorem 8.3.1

If A is a subset of the set N, such that

  1. 0 ∈ A, and
  2. for every natural number n holds:
    if k ∈ A for every k<n+1 then n+1 ∈ A,

then A=N.

Proof.

If both the assumption 1 as well as 2 of the theorem 8.3.1 are satisfied and A ≠ N, then the set N\A is non-empty. Now we take its smallest element n0 (according to the minimum principle such an element exists). Thus, we obtain n0 ≠ 0 (in obedience to assumption 1 zero belongs to the set A).

Because n0 is the smallest element of the set N\A, then all numbers less than n0 do not belong to this set but up to the set A. It follows that in accordance with the assumption 2, we conclude that n0 ∈ A. Contradiction. ♦

Example 8.3.1

For any a>-1 and any natural number n, holds (1+a)n ≥ 1 + n a.

Solution

Let PT(n) be the following property (1+a)n ≥ 1+ n a.

Induction base: Because (1+a)0 ≥ 1 thus, PT(0) holds.

Induction assumption: Let's assume that for some k is PT(k), i.e. (1+a)k ≥ 1+ ka.

Induction thesis: PT(k+1) holds i.e. (1+a)k+1 ≥ 1+ (k+1)a.

Thesis proof: (1+a)k+1 = (1+a)k (1+a). By the induction assumption we have: (1+a)k+1 ≥ (1+ ka)(1+a) ≥ 1 + ka + a + kaa ≥ 1+ (k+1)a + ka2.

Notice that ka2 ≥ 0, thus, finally, (1+a)k+1 ≥ 1+ (k+1)a. That is why (k+1) has the PT property. Because the induction principle assumptions 1 and 2 are satisfied, then we conclude that the proposition PT(n) holds for all natural numbers n.


Question 8.3.1 Is the assumption a>-1 important for the problem presented above? Where do we use it?

----- Check the answer -----

How to prove properties that are valid not for all natural numbers but for almost all numbers?  It happens sometimes that we need to prove a theorem which holds for integers greater than some fixed number. Can we apply the principle of induction?  The answer is - yes. The following form of mathematical induction may be helpful in these cases:

Theorem 8.3.2

Let m be an integer number and let α(n) be a proposition over set {n ∈ Z : n ≥ m}. If

  1. proposition α (m) is valid and
  2. validity of  all propositions α(m), α(m+1),..., α(k-1) for some k>m, implies the validity of α(k),

then α(n) is valid for any integer n ≥ m.

Proof.

Denote the proposition α(m+n) by PT(n). Let us assume that both conditions of the theorem 8.3.2  hold. Hence, by the first condition   PT(0) is valid. Let's assume that properties PT(0), ..., PT(k-1) are valid. This implies, in accordance to the property PT definition, that all propositions α(m), α(m+1),..., α(m+k-1) are valid. Thus, by the second  assumption of theorem 8.3.2, proposition α(m+k) is valid too. In consequence  PT(k) is valid.

We have shown in this way, that if properties PT(0), ..., PT(k-1) are valid for some k, then so is   PT(k). Now, we can apply theorem 8.3.1 and conclude that all proposition PT(n) are valid and therefore all proposition α(n) are valid for any n ≥ m. ♦

The version of the induction principle discussed above is very helpful when proving the following lemma:

Lemma 8.3.2

For any n>1 and for any finite sets X1, X2, ..., Xn, it holds that

| X1 × X2 × ... × Xn| = | X1 | ⋅ | X2 | ⋅ ... ⋅ |Xn|.

Proof.

Proof's part one. At the beginning, we will show that for any finite sets X1, X2 ,  |X1 × X2| = |X1| ⋅ |X2|. In order to do that, we conduct an induction on the number of elements of the set X2. If the set X2 is empty then we cannot create any ordered pair, the second element of which belongs to X2. Thus, |X1 × X2| = 0 = |X1| ⋅ |X2|.

Let's assume (induction assumption) that  |X1 × X2| = |X1| ⋅ |X2| is valid when |X2| = k. Now we consider a (k+1)-element set X = {a1, a2, ..., ak+1}. All pairs in the product X1 × X may be divided into two groups:

  1. pairs of form (x, ak+1) for x ∈ X1,
  2. pairs in which the second element is different from a k+1.

 

There are as many pairs of group 1 as the number of elements in the set X1, i.e. |X1|. The number of pairs of the second type is equal to the cardinality of product X1 × {a1, a2, ..., ak}. According to the induction assumption |X1 × {a1, a2, ..., ak}| = |X1| ⋅ k, therefore |X1 × X| = |X1| ⋅k + |X1| = |X1| ⋅ (k+1).

We have proved that, if equality |X1 × X2| = |X1| ⋅ |X2| holds for the k-element set X2, then it is also satisfied for the (k+1)-element set X2. According to the induction principle, the formula |X1 × X2| = |X1| ⋅ |X2| is valid for all  finite sets X1 , X2.

Denote by α(n) the equality mentioned in lemma 8.3.2. The first part of the proof show that the proposition α(2) is valid.  This is the base of our  induction.

Proof's part two. Now, let's assume that α(k) is valid for some k ∈ N (induction assumption). Our task is to show that α(k+1) is also satisfied.

Let X1, X2, ..., Xk+1 be freely chosen finite sets. Notice, that every element (x1, x2, ..., xk, xk+1) of the product X1 × ... × Xk × Xk+1 can be unambiguously ascribed to an ordered pair (a, xk+1), where a = (x1, x2, ..., xk). It follows that the number of different elements of the form (x1, x2, ..., xk, xk+1) is equal to the number of ordered pairs of the form  ((x1, x2, ..., xk), xk+1). Thus, we obtain

| X1 × X2 × ... × Xk × Xk+1| = | X1 × X2 × ... × Xk| ⋅ |Xk+1|.

In accordance with the induction assumption | X1 × X2 × ... × Xk| = | X1 | ⋅ | X2 | ⋅ ... ⋅ |Xk|. This equality with the previous one shows together that the proposition α(k+1) is valid.

Both assumptions of theorem 8.3.2 are satisfied, thus proposition α(n) is valid for all natural numbers n >1.

Question 8.3.2 Try to find other arguments proving that cardinality of the product of two finite sets is equal to the product of cardinalities of these sets.   ♦

----- Check the answer -----


In closing this subsection we consider the case when a property which we are trying to prove concerns only  some finite subset of natural numbers. This type of induction method is called finite induction principle.

Theorem 8.3.3

Let m and k be natural numbers and let α(n) be a proposition expressing some property of natural number n,  m ≤ n ≤ k. If

  1. the proposition α (m) is valid and
  2. the validity of the proposition α(i)  for some m ≤ i < k implies the validity of the proposition  α(i+1),

then α(n) is satisfied for any n ≥ m and n ≤ k.

Question 8.3.3  Prove that n! > 2n for every natural number n ≥ 4. Which version of the induction principle should be used?


----- Check the answer -----


« previous section    next section »