Linear Algebra and Analysis

1.4 Well Ordering And Induction

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.

In particular, the natural numbers defined as

ℕ ≡ {1,2,⋅⋅⋅}

is well ordered.

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.

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

T. Thus b ≥ a + 1, and so b − 1 ≥ a and b − 1S because if b − 1 ∈ S, then b − 1 + 1 = b ∈ S by the assumed property of S. Therefore, b − 1 ∈ T which contradicts the choice of b as the smallest element of T. (b − 1 is smaller.) Since a contradiction is obtained by assuming T≠∅, it must be the case that T = ∅ and this says that every integer at least as large as a is also in S. ■

Mathematical induction is a very useful device for proving theorems about the integers.

▸

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

n+∑1 2 ∑n 2 2 n(n + 1)(2n + 1) 2 k = k +(n + 1) = -------6-------+ (n+ 1) . k=1 k=1

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,

n(n + 1) (2n + 1) 2 -------6-------+ (n+ 1) .

This equals

( ) (n+ 1) n(2n+-1)-+ (n + 1) 6

and

n (2n + 1) 6(n+ 1)+ 2n2 + n (n+ 2)(2n+ 3) ---------+ (n+ 1) = ---------------- = -------------- 6 6 6

Therefore,

n∑+1 (n + 1)(n+ 2)(2n+ 3) (n+ 1)((n+ 1)+ 1)(2(n +1) +1) k2 = ---------6----------= --------------6--------------, k=1

showing the formula holds for n + 1 whenever it holds for n. This proves the formula by mathematical induction.

If n = 1 this reduces to the statement that

< which is obviously true. Suppose then that the inequality holds for n. Then

√------ 1 3 2n-−-1 2n-+-1 ---1---2n-+-1 -2n-+-1 2 ⋅4 ⋅⋅⋅ 2n ⋅2n + 2 < √2n + 12n + 2 = 2n + 2 .

The theorem will be proved if this last expression is less than

. This happens if and only if

( )2 √--1--- = --1---> -2n-+-12 2n + 3 2n+ 3 (2n+ 2)

which occurs if and only if

² > and this is clearly true which may be seen from expanding both sides. This proves the inequality.

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.