1.2. WELL ORDERING AND INDUCTION 3

b− 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.2.4 Prove by induction thatn

∑k=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.2.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.