1.4. WELL ORDERING AND INDUCTION 7

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 1.4.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.

Example 1.4.5 Show that for all n ∈ N,12· 3

4· · · 2n−1

2n<

1√2n+1

.

If n = 1 this reduces to the statement that12<

1√3

which is obviously true. Suppose

then that the inequality holds for n. Then

12· 3

4· · · 2n−1

2n· 2n+1

2n+2<

1√2n+1

2n+12n+2

=

√2n+1

2n+2.