1.7. WELL ORDERING PRINCIPLE, MATH INDUCTION 27

Example 1.7.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 theformula 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)

)and

n(2n+1)6

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

6=

(n+2)(2n+3)6

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

6 = (n+1)((n+1)+1)(2(n+1)+1)6 , showing that the formula

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

Example 1.7.5 Show that for all n ∈ N, 12 ·

34 · · ·

2n−12n < 1√

2n+1.

If n = 1 this reduces to the statement that 12 < 1√

3which 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

The theorem will be proved if this last expression is less than 1√2n+3

. This happens if and

only if(

1√2n+3

)2= 1

2n+3 > 2n+1(2n+2)2 if and only if (2n+2)2 > (2n+3)(2n+1) 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 followsn+ 1 ∈ S. Therefore, by the principle of mathematical induction, S contains [1,∞)∩Z,all positive integers. In doing an inductive proof of this sort, the set, S is normally notmentioned. One just verifies the steps above. First show the thing is true for some a ∈ Zand then verify that whenever it is true for m it follows it is also true for m+1. When thishas been done, the theorem has been proved for all m ≥ a.

Definition 1.7.6 The Archimedean property states that whenever x ∈ R, and a > 0,there exists n ∈ N such that na > x.

This is not hard to believe. Just look at the number line. Imagine the intervals

[0,a), [a,2a), [2a,3a), · · · .

If x < 0, you could consider a and it would be larger than x. If x ≥ 0, surely, it is reasonableto suppose that x would be on one of these intervals, say [pa,(p+1)a). This Archimedeanproperty is quite important because it shows every fixed real number is smaller than someinteger. It also can be used to verify a very important property of the rational numbers.