184 METHODS OF MATHEMATICAL PROOF, PART I Chapter 5The resblts in Examples 5 and 6, when combined with an elementary
summation formula such as x;=, k = [n(n + 1)]/2 [recall Example l(b)]
can be used to produce quick and easy (noninduction) proofs of additional
summation properties. For example, we may prove that x;=, (4k - 5) =
2n2 - 3n for all n E N by either an induction argument or by the argument:You should supply justifications for each step of this argument, and see
Exercise 4 for similar type problems.Results about divisibility. If a and b are integers, we say that a divides b,
denoted a1 b, if and only if there exists an integer n such that b = nu. In
Article 6.1 we will verify a number of properties of divisibility, the results
of which we assume and use for the time being. These include:- ala for all aEZ
- Va,b,c~Z, ifalb, then albc
- ~a,b,c~Z,ifalbandalc, thenal(b+c)
- Va,b,c~Z, ifalb and blc, then alc
A number of properties of divisibility are valid "for all positive integers n,"
and hence lend themselves to proof by induction. The next example pre-
sents one such property.' EXAMPLE 7 Prove that 6 divides 7" - 1 for all positive integers n.
Solution Define S in the usual fashion. Note that 1 E S since 7' - 1 = 6 and
6 divides itself. Now suppose m E S. To prove m + 1 E S, we must prove
that 6 divides 7"" - 1, using the inductive assumption that 6 divides
7" - 1. Now 7"" - 1 = 7(7" - 1) + 6. Since 6 divides 7" - 1, then 6
divides 7(7" - 1) by (2). Clearly 616 [by (I)]. By (3), we have that 6
divides the sum of 6 and 7(7" - 1). But this sum equals 7"+l - 1, so
that 6 divides 7"" - 1, as we wished to prove.INDUCTIVE SETS
Part (c) of Example 1 is a theorem that is true not for all positive integers,
but rather, for all integers greater than or equal to a particular positive
integer no, in this case no = 5. A slight variation in the induction principle
, can be used to prove theorems of this type. We introduce a concept helpful
b toward this end in Definition 1.
I
I