Mathematical induction and well ordering are two extremely important principles in math. They are often used to prove significant things which would be hard to prove otherwise.
Definition 1.4.1 A set is well ordered if every nonempty subset S, contains a smallest element z having the property that z ≤ x for all x ∈ S.
Axiom 1.4.2 Any set of integers larger than a given number is well ordered.
In particular, the natural numbers defined as
|
The above axiom implies the principle of mathematical induction. The symbol ℤ denotes the set of all integers. Note that if a is an integer, then there are no integers between a and a + 1.
Theorem 1.4.3 (Mathematical induction) A set S ⊆ ℤ, having the property that a ∈ S and n + 1 ∈ S whenever n ∈ S contains all integers x ∈ ℤ such that x ≥ a.
Proof: Let T consist of all integers larger than or equal to a which are not in S. The theorem will be proved if T = ∅. If T≠∅ then by the well ordering principle, there would have to exist a smallest element of T, denoted as b. It must be the case that b > a since by definition, a
Mathematical induction is a very useful device for proving theorems about the integers.
Example 1.4.4 Prove by induction that ∑ k=1nk2 =
By inspection, if n = 1 then the formula is true. The sum yields 1 and so does the formula on the right. Suppose this formula is valid for some n ≥ 1 where n is an integer. Then
|
The step going from the first to the second line is based on the assumption that the formula is true for n. This is called the induction hypothesis. Now simplify the expression in the second line,
|
This equals
|
and
|
Therefore,
|
showing the formula holds for n + 1 whenever it holds for n. This proves the formula by mathematical induction.
Example 1.4.5 Show that for all n ∈ ℕ,
If n = 1 this reduces to the statement that
|
The theorem will be proved if this last expression is less than
|
which occurs if and only if
Lets review the process just used. If S is the set of integers at least as large as 1 for which the formula holds, the first step was to show 1 ∈ S and then that whenever n ∈ S, it follows n + 1 ∈ S. Therefore, by the principle of mathematical induction, S contains [1,∞) ∩ ℤ, all positive integers. In doing an inductive proof of this sort, the set S is normally not mentioned. One just verifies the steps above. First show the thing is true for some a ∈ ℤ and then verify that whenever it is true for m it follows it is also true for m + 1. When this has been done, the theorem has been proved for all m ≥ a.