Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 11] PROPERTIES OF THE INTEGERS 267

SupposeP(k)is true. (This is called the inductive hypothesis.) Adding 2k+1 to both sides ofP(k)we

obtain

1 + 3 + 5 +···+( 2 k− 1 )+( 2 k+ 1 )=k^2 +( 2 k+ 1 )

=( 2 k+ 1 )^2

which isP(k+ 1 ). We have shown thatP(k+ 1 )is true wheneverP(k) is true. By the principle of

mathematical induction,Pis true for all positive integersn.

(b) The symboln! (read:nfactorial) is defined as the product of the firstnpositive integers; that is:

1 != 1 , 2 != 2 · 1 = 2 , 3 != 3 · 2 · 1 = 6 , and so on.

This may be formally defined as follows:

1 !=1 and (n+ 1 )!=(n+ 1 )(n!), for n> 1

Observe that ifSis the set of positive integers for which! is defined, thenSsatisfies the two properties of

mathematical induction. Hence the above definition defines! for every positive integer.

There is another form of the principle of mathematical induction (proved in Problem 11.13) which is some-
times more convenient to use. Namely:

Theorem 11.5 (Induction: Second Form): LetPbe a proposition defined on the integersn≥1 such that:

(i) P( 1 )is true.

(ii) P(k)is true wheneverP(j )is true for all 1≤j<k.

ThenPis true for every integern≥1.

Remark:Theabovetheorem is true if we replace 1 by 0 or by any other integera.

Well-Ordering Principle

A property of the positive integers which is equivalent to the principle of induction, although apparently very
dissimilar, is the well-ordering principle (proved in Problem 11.12). Namely:

Theorem 11.6 (Well-Ordering Principle): LetSbe a nonempty set of positive integers. ThenScontains a
least element; that is,Scontains an elementasuch thata≤sfor everysinS.
Generally speaking, an ordered setSis said to bewell-orderedif every subset ofScontains a first element.
Thus Theorem 11.6 states thatNis well ordered.
A setSof integers is said to bebounded from belowif every element ofSis greater than some integerm
(which may be negative). (The numbermis called alower boundofS.) A simple corollary of the above theorem
follows:

Corollary 11.7: LetSbe a nonempty set of integers which is bounded from below. ThenScontains a least
element.

11.4Division Algorithm

The following fundamental property of arithmetic (proved in Problems 11.17 and 11.18) is essentially a
restatement of the result of long division.

Theorem 11.8 (Division Algorithm): Letaandbbe integers withb=0. Then there exists integersqandr
such that
a=bq+r and 0≤r<|b|
Also, the integersqandrare unique.