2.7. WELL ORDERING AND ARCHIMEDEAN PROPERTY 19

numbers from Sn? Obviously one way. Note the above formula gives the right answer inthis case as well as in all other cases due to the definition which says 0! = 1.

Now consider the problem of writing a formula for (x+ y)n where n is a positive integer.Imagine writing it like this:

n times︷ ︸︸ ︷(x+ y)(x+ y) · · ·(x+ y)

Then you know the result will be sums of terms of the form akxkyn−k. What is ak? Inother words, how many ways can you pick x from k of the factors above and y from theother n− k. There are n factors so the number of ways to do it is

(nk

). Therefore, ak is the

above formula and so this proves the following important theorem known as the binomialtheorem.

Theorem 2.6.1 The following formula holds for any n a positive integer.

(x+ y)n =n

∑k=0

(nk

)xkyn−k.

2.7 Well Ordering and Archimedean PropertyDefinition 2.7.1 A set is well ordered if every nonempty subset S, contains a small-est element z having the property that z≤ x for all x ∈ S.

Axiom 2.7.2 Any set of integers larger than a given number is well ordered.

In particular, the natural numbers defined as N≡{1,2, · · ·} is well ordered.The above axiom implies the principle of mathematical induction.

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

Proof: Let T ≡ ([a,∞)∩Z) \ S. Thus T consists of all integers larger than or equalto a which are not in S. The theorem will be proved if T = /0. If T ̸= /0 then by the wellordering principle, there would have to exist a smallest element of T, denoted as b. It mustbe the case that b > a since by definition, a /∈ T. Then the integer, b−1 ≥ a and b−1 /∈ Sbecause if b− 1 ∈ S, then b− 1+ 1 = b ∈ S by the assumed property of S. Therefore,b−1 ∈ ([a,∞)∩Z)\S = 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 ̸= /0, it must be the casethat T = /0 and this says that everything in [a,∞)∩Z is also in S.

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

Example 2.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 .