26 CHAPTER 1. FUNDAMENTAL CONCEPTS

Now consider the number of ways of selecting a set of k different numbers from Sn. Foreach set of k numbers there are P(k,k) = k! ways of listing these numbers in order. There-

fore, denoting by

(n

k

)the number of ways of selecting a set of k numbers from Sn, it

must be the case that (n

k

)k! = P(n,k) =

n!(n− k)!

Therefore,

(n

k

)= n!

k!(n−k)! . How many ways are there to select no numbers from Sn?

Obviously one way. Note that the above formula gives the right answer in this case as wellas 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? In otherwords, how many ways can you pick x from k of the factors above and y from the other

n−k. There are n factors so the number of ways to do it is

(n

k

). Therefore, ak is

(n

k

)and so this proves the following important theorem known as the binomial theorem.

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

(x+ y)n =n

∑k=0

(n

k

)xkyn−k.

1.7 Well Ordering Principle, Math InductionDefinition 1.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 1.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 1.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.