2.2. WELL ORDERING AND INDUCTION 17

In particular, the natural numbers defined as

N≡{1,2, · · ·}

is well ordered.The above axiom implies the principle of mathematical induction. The symbol Z de-

notes the set of all integers. Note that if a is an integer, then there are no integers betweena and a+1.

Theorem 2.2.3 (Mathematical induction) A set S ⊆ Z, having the property that a ∈ S andn+1 ∈ S whenever n ∈ S contains all integers x ∈ Z such that x≥ a.

Proof: Let T consist of all integers larger than or equal to a which are not in S. Thetheorem will be proved if T = /0. If T ̸= /0 then by the well ordering principle, there wouldhave to exist a smallest element of T, denoted as b. It must be the case that b > a since bydefinition, a /∈ T. Thus b≥ a+1, and so b−1≥ a and b−1 /∈ S because if b−1 ∈ S, thenb− 1+ 1 = b ∈ S by the assumed property of S. Therefore, b− 1 ∈ T which contradictsthe choice of b as the smallest element of T. (b− 1 is smaller.) Since a contradiction isobtained by assuming T ̸= /0, it must be the case that T = /0 and this says that every integerat least as large as a is also in S. ■

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

Example 2.2.4 Prove by induction that ∑nk=1 k2 =

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

.

▶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

∑k=1

k2 =n

∑k=1

k2 +(n+1)2 =n(n+1)(2n+1)

6+(n+1)2 .

The step going from the first to the second line is based on the assumption that the formulais true for n. This is called the induction hypothesis. Now simplify the expression in thesecond line,

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

+(n+1)2 .

This equals

(n+1)(

n(2n+1)6

+(n+1))

andn(2n+1)

6+(n+1) =

6(n+1)+2n2 +n6

=(n+2)(2n+3)

6Therefore,

n+1

∑k=1

k2 =(n+1)(n+2)(2n+3)

6=

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

,

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