An Introduction to Mathematical Proof 1

An Introduction to Mathematical Proof1

Chapter 3

Teaching Notes, Chapter 3: The preparation of middle-grades mathematics teachers sometimes does not include experience with reading and writing careful mathematical arguments. Since we must provide middle-grades teachers with not only the specific knowledge they will teach but also the mathematical context for that knowledge, experience with reading and writing proofs is an essential part of their preparation.

There are at least three paths that can be taken through Chapter 3. For classes involving students from a variety of backgrounds, you might choose to spend a day or two on Section 3.1 with the dual goals of helping the students understand the pitfalls to inductive thinking that make mathematical proofs necessary and how simple deductive arguments related to even and odd numbers and divisibility can overcome those difficulties. In this case you would want to give careful attention to examples where a pattern seems to exist, but closer examination produces a counterexample.

A second path would involve study of Sections 3.1, 3.2, and 3.3. This will introduce all the proof techniques used later in the text and provide students the opportunity to practice those techniques in a variety of circumstances.

The third path would involve the study of all five sections in the chapter. Because Sections 3.4 and 3.5, together with 3.1, provide students with a brief introduction to number theory, this allows you to broaden the set of topics covered in the course. Further, the task of proving some of the simple theorems of number theory provides an immediate opportunity for students to practice their newly acquired skills in theorem proving.

Teaching Notes, Section 3.1: A primary objective of this section involves helping students understand why mathematical proof is necessary; why it is not sufficient just to observe a pattern in a few examples. Careful attention to the discussion of the first two pages of Section 3.1 and Exploratory Exercises 3 and 4 will assist in this objective.

In this section we begin a theme we will continue throughout the remaining sections and chapters: Before attempting a proof one must spend some time in preparation. If you intend to join the authors in emphasizing this theme, it is important to model that preparation as you discuss the simple theorems of this section with the students. Trying examples and testing conjectures is a first step; reviewing related definitions and theorems, a second; and a moment or so of reflection in which you devise a plan to connect known information with the theorem to be proved, a third.

We recommend having students work in groups on Exploratory Exercises 1 and 2 and Exercise 7 before sending them home to work on problems alone.

Exploratory Exercise Set 3.1

(a) An integer n is odd provided that there is an integer k with n = 2k + 1. 27 is odd because

13 is an integer with 27 = 2(13) + 1.

(b) An integer n is even provided that there is an integer k with n = 2k. 202 is even because 101 is an integer with 202= 2(101).

(d)Answers will vary. For example, 5 + 7 = 12.

(e)Therefore x + y = (2m + 1) + (2n + 1) = 2m + 2n + 2 = 2(m + n + 1). Since m + n + 1 is an integer, x + y is even.

(f)If we had used the same letter to represent both x and y as an odd integer (for example, x = 2k + 1 and y = 2k + 1), the notation would have suggested that x and y are the same number.

(g)Theorem 3.

Examples would include sums such as 4 + 3 = 7.

Conjecture:If x is an even integer and y is an odd integer, then x + y is an odd integer.

Proof: Since x is an even integer, there is an integer m with x = 2m. Since y is an odd integer, there is an integer n with y = 2n + 1. Therefore x + y = 2m + (2n + 1) = 2m + 2n + 1 = 2(m + n)+ 1. Since m + n is an integer, x + y is odd.

This is a proof of Theorem 4.

3. (a)

n / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9
f(n) / 41 / 43 / 47 / 53 / 61 / 71 / 83 / 97 / 113
Factors / 1, 41 / 1, 43 / 1, 47 / 1, 53 / 1, 61 / 1, 71 / 1, 83 / 1, 97 / 1, 113
Is f(1) prime? / Yes / Yes / Yes / Yes / Yes / Yes / Yes / Yes / Yes

(b) f(n) is a prime number for all positive integers n.

(d)The conjecture is not true.

(e)Even though we may find many examples that suggest the pattern represented in a conjecture, we cannot know that the conjecture is always true until we have designed a proof of the conjecture.

(a) 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

(b)

p / / Positive divisors of / Is it a prime?
2 / 22 – 1 = 3 / 1, 3 / Yes
3 / 7 / 1, 7 / Yes
5 / 31 / 1, 31 / Yes
7 / 127 / 1, 127 / Yes

(c)If n is of the form where p is a prime, then n is a prime number.

(d) Since 2047 = 23 · 89, 2047 is not a prime.

Answers will vary.

Exercise Set 3.1

1. (a) 9 is an integer with 27 = 3 · 9.(b) 0 is an integer with 0 = 12 · 0.

(e) 6y is an integer with 6xy = x(6y).(f) st is an integer with rst = r(st).

2.(a) 1, 2, 4, 8, 16(b) 1, 2, 3, 4, 6, 8, 12, 24 (c) 1, 2, 3, 6, 7, 14, 21, 42

3. (a) There is no integer k with 7 = 0 · k.(b) 7 is an integer with 42 = 6 · 7.

(d) The only positive divisors of 17 are 1 and 17.

(e)The only divisors of 2 are 1 and 2. 2 is a divisor of all other even numbers.

4. (a) 7 is a factor of 28. (b) 5 is not a factor of 36.

5. (a) 28 is divisible by 7. (b) 36 is not divisible by 5.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71

7. (a) Yes, 3 | (12 + 24) since 12 + 24 = 3 · 4 + 3 · 8 = 3 · (4 + 8) = 3 · 12.

(b) Yes, 5 | (25+ 15) since 25 + 15 = 5 · 5 + 5 · 3 = 5 · (5 + 3) = 5 · 8.

(d) b = ak; c = am; k + m; integer(e) Theorem 7

8. Since a | b, there is an integer k with b = ak. Since a | c, there is an integer m with c = am. Since a | d, there is an integer n with d = an. Therefore, (b + c + d) = ak + am + an = a(k + m + n). Since k + m + n is an integer, a | (b + c + d).

9. (a) Yes, since 12 · 5 = (4 · 3) · 5 = 4 · (3 · 5) = 4 · 15.

(b) Yes, since 6 · 11 = (3 · 2) · 11 = 3 · (2 · 11) = 3 · 22.

(d) b = ak; kn; a | bn (e) Theorem 9

10. (a) 3 | 6 and 6 | 18 and certainly 3 | 18 since 18 = 6(3).

(b)Answers will vary. For example, 11 | 22 and 22 | 66. Note that 11 | 66.

(c)Since a | b, there is an integer k with b = ak. Since b | c, there is an integer n with c = bn. Replacing b in this last equality by ak yields c = (ak)n = a(kn). Since kn is an integer,

a | c.

11. (a) Answers vary; for example 3 · 11 = 33 which is odd.

(b) If x and y are odd integers, then xy is an odd integer.

(c) Since x is odd, there is an integer k with x = 2k + 1. Since y is odd, there is an integer j with y = 2j + 1. Then xy = (2k + 1)(2j + 1). Using the properties of addition and multiplication of integers, we can rewrite this as:

xy = 4kj + 2k + 2j + 1 = 2(2kj + k + j) + 1

Since 2kj + k + j is an integer, xy is an odd integer.

(d)Theorem 5

(a) Answers will vary. For example, 4 · 6 = 24.

(b) If x is an even integer and y is an integer, then xy is an even integer.

(c)Since x is even, there is an integer k with x = 2k. Then xy = (2k)(y). Using the properties of

addition and multiplication of integers, we can rewrite this as:

xy = 2(ky)

Since ky is an integer, xy is an even integer.

(d) Theorem 6

13. (a) 7(100) + 4(10) + 4(b) According to the Rule of 2, since 2 | 4, 2 | 744.

14. (a) 6(100) + 5(10) + 4(b) According to the Rule of 3, since 3 | (6 + 5 + 4) , 3 | 654.

(d) a(99 + 1) +b(9 + 1) + c = a(99) + a(1) + b(9) + b(1) + c = a(99) + b(9) + (a + b + c).

99 = 3 · 33; Theorem 9; 9 = 3 · 3; Theorem 9

By Theorem 8, 3 | a(99) + b(9) + (a + b + c) and hence 3 | z.

15. z can be written in expanded notation as z = a(100) + b(10) + c.

4 | 100 since 100 = 4(25). Therefore 4 | [a(100)] by Theorem 9.

By hypothesis, 4 divides the number formed by the rightmost two digits of z, that is,

4 | [b(10) + c]. Since 4 | [a(100)] and 4 | [b(10) + c], then by Theorem 7, 4 | z.

16. z can be written in expanded notation as z = a(100) + b(10) + c.

5 | 100 since 100 = 5(20). Therefore 5 | [a(100)] by Theorem 9.

5 | 10 since 10 = 5(2). Therefore 5 | [b(10)] by Theorem 9.

17.z can be written in expanded notation as z = a(100) + b(10) + c.

100 = 99 + 1; 10 = 9 + 1.

Therefore z = a(99 + 1) +b(9 + 1) + c = a(99) + b(9) + a·1 + b·1 + c = a(99) + b(9) + (a + b + c).

9 | 99 since 99 = 9·11. Therefore 9 | [a(99)] by Theorem 9.

9 | 9 since 9 = 9 · 1. Therefore 9 | [b(9)] by Theorem 9.

9 | (a + b + c) is the hypothesis of the “Rule for 9.”

It follows by Theorem 8 that 9 divides a(99) + b(9) + (a + b + c) and hence 9 | z.

18. z can be written in expanded notation as z = a(100) + b(10) + c

=a(99 + 1) + b(11 – 1) + c

=a(99) + a + b(11) – b + c

=a(99) + b(11) + (a – b + c)

11 | 99 since 99 = 11·9. Therefore 11 | [a(99)] by Theorem 9.

11 | 11 since 11 = 11·1. Therefore 11 | [b(11)] by Theorem 9.

11 | (a – b + c) is the hypothesis of the “Rule for 11.”

It follows by Theorem 8 that 11 divides a(99) + b(11) + (a – b + c) and hence 11| z.

19. (a) We would write the integers in expanded form as a(1000) + b(100) + c(10) + d and

then make the arguments looking at the divisibility properties of this decomposition.

(d) z can be written in expanded notation as z = a(1000) + b(100) + c(10) + d.

2 | 1000 since 1000 = 2(500). Therefore 2 | [a(1000)] by Theorem 9. 2 | 100 since

100 = 2(50). Therefore 2 | [b(100)] by Theorem 9. 2 | 10 since 10 = 2(5).

Therefore 2 | [c(10)] by Theorem 9. “2 | d” is the hypothesis of the “Rule for 2.”

Since 2 | [a(1000)] and 2 | [b(100)] and 2 | [c(10)] and 2 | d, then by (c) of this

exercise, 2 | z.

(a) a | a because a = a · 1. Thus | is reflexive.

(b)In Exercise 10 we proved that if a | b and b | c, then a | c. This is the statement of the transitive property for “divides.”

(d)Since a | b there is an integer k with a = bk. Since b | a there is an integer n with b = an. Replacing a by bk in the second equation yields b = bkn. Thus kn = 1 meaning k = n = 1 or k = n = – 1. Since a and b are positive, the desired result follows.

Teaching Notes, Section 3.2: Depending on the level of preparation of your students, you may want to do much of the work of this section in groups. At the very least, have students work on Exploratory Exercises 1 and 2 before sending them home to work on problems alone.

The collection of exercises, Exercises 11 through 15, provide the basis of a good group or individual project to summarize the material learned in Sections 3.1 and 3.2.

Exploratory Exercise Set 3.2

1. (a) A (BC) = {s, t} and (AB)  (AC) = {s, t}

(b) Find in text.

(d) Definition of intersection; definition of union; Looking back at the two previous statements we see that a is definitely an element of A and it is also in either B or C; a is an element of either (AB) or (AC) and hence by definition is in the union of these two sets.

Each element of A (BC) is an element of (AB)  (AC).

(e) Let a  (AB)  (AC). Then by the definition of union, a  (AB) or a  (AC). If a  (AB), then a A and a B. Similarly, if a  (AC), then a A and a C. In either case, a A. Further, a B or a C. By the definitions of intersection and union, aA(BC).

(f) Since A (BC)(AB)  (AC)and (AB)  (AC)A (BC),the two sets are equal.

2. (a) 2 + ; Answers will vary. For example 1 +

(b)Find in text.

Since y is an irrational number, it by definition cannot be written as quotient of two integers.

(d) ; , ; Subtracting from both sides of the equation yields

y == . Since nk – ml is an integer and nl is a non-zero integer, this is a contradiction of the hypothesis that y is irrational.

(e) We assumed that the negation of this statement is true and this led to a contradiction. Therefore the statement itself must be true.

3. (a) (1) 1. 3 | (1 – 4) and 3 | (4 – 1)

2. 3 | (5 – 2) and 3 | (2 – 5)

3. 3 | (0 – 6) and 3 | (6 – 6)

(2)Find in text.

(3)Reflexive, symmetric, transitive

(b) (1) 3 | (a – a)

(2) ba; (a – b) = 3k; Therefore – (a – b) = – 3k or (b – a) = 3(–k). Thus 3 | (b – a) or ba.

(3) a c; (a – b) = 3k; 3 | (b – c); (b – c) = 3l; Thus (a – b) + (b – c) = 3k + 3l or

(a – c) = 3k + 3l = 3(k + l). Thus 3 | (a – c) or a c.

Exercise Set 3.2

1. (a) {v, w}

(b) Find in this section.

2. (a) Let x AB. We will show that this means x A.

(b) (1) A, B

(2) A

3. (a) AB = {1, 2, 3, 5}. Since every element of A is an element of AB, AAB.

(b)See Preparation for Theorems 10 and 11.

(c) The first sentence in our proof will be, “Let a be an arbitrary element of A.” We will then try to show that a must be an element of AB.

(d) Let a be an arbitrary element of A. By the definition of AB, a is also an element of

AB. Thus AAB.

4. First do preparation similar to that done prior to the proof of Theorem 11. Choose sets A and B and work through an example, review the definitions of intersections, unions and complements of sets, and reflect on a strategy for showing two sets are equal.

Show. Let x. Then x. Said another way, “it is not true that xA and xB.” We can rewrite this statement using DeMorgan’s Laws for the negation of conjunction as “x A or xB.” Thus x or x . By definition of union, x .

Show. Let x. Then x or x. Said in words, “x is not an element of A or x is not an element of B.” By DeMorgan’s Law for negation of conjunction, this statement can be rewritten as “It is not true that x is an element of A and x is an element of B.”

xAB. x .

Since we have now shown set containment in both directions, we have shown that the two sets are equal.

5. First do preparation similar to that done in Exploratory Exercise 1. Choose sets A, B, and C and work through an example, review the definitions of intersection and union of sets and reflect on a strategy for showing two sets are equal.

Show that A (BC)  (AB)  (AC).

Let a A (B C). Then, by definition of union, a A or a BC. If a A then the definition of union ensures that a is an element of both (AB) and (AC). If a BC, then by definition of intersection, a B and a C. It follows that in either case a is an element of both (AB) and (AC). Thus a(AB)(AC) and we have proved A(BC)  (AB)  (AC).

The proof can then be finished by showing that (AB)  (AC) A (BC) using a similar argument.

First do preparation similar to that done in Exploratory Exercise 2. Look at several products of the form (rational number)(irrational number), review the definitions of rational and irrational numbers and review the way one formulates a proof by contradiction.

Suppose x is a non-zero rational number, y is an irrational number and xy is a rational number. Since x is rational, there are integers m and n (n0)with x = . Further, since x is non-zero, m 0. Since we are supposing xy is rational, there are integers k and l (l0) with xy = . By replacing x with , we see that y = or y = . Since nk is an integer and ml is a non-zero integer, this result contradicts our assumption that y is irrational.

7. (a) Let x = and let y = where j, k, m, and n are integers and k and n are

not equal to 0. Then x + y = . Since and kn are integers and

kn is not equal to 0, then x + y is a rational number.

(b) Let x = and let y = where j, k, m, and n are integers and k and n are

not equal to 0. Then xy = . Since and kn are integers and kn is not

equal to 0, then xy is a rational number.

x + y = 0 which is a rational number.

(d) False. Let x = and let y = . Both and  are irrational

numbers, but xy = 2 which is a rational number.

9. (a) x – y = x + (–1)y. Since d | y, then, by Theorem 9, d | (–1)y. It follows from

Theorem 7 that if d | x and d | (–1)y, then d | (x + (–1) y) or d | x – y.

(b) Since a = bq + r, then r = a – bq. Since d | a and d | b, d | bq by Theorem 9 and

d | r by the result in (a).

10. (a) If n is not even, then n2 is not even. Alternatively, If n is odd, then n2 is odd.

(b) Since n is odd, then by Theorem 5, n · n = n2 is odd.

11. (a) 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 36; 3 · 6 = 18, 3 · 9 = 27, 3 · 12 = 36, 9 · 12 =

108. In each case the product of two smooth integers is smooth.

(b) If x and y are smooth, then xy is smooth.

there is an integer j with y = 3j. Then xy = (3k)(3j) = 9kj = 3(3kj). Since 3kj is an integer, xy is three times an integer, and hence xy is smooth.

12. (a) Answers will vary. For example, 7 = 2(3) + 1 and 13 = 4(3) + 1 are rough integers and since (7)(13) = 91 = 3(30) + 1, their product is rough.

(b) If x and y are rough integers, xy is rough.

rough, there is an integer j with y = 3j+ 1. Then xy = (3k + 1)(3j + 1) = 9kj +3k + 3j + 1 = 3 (3kj + k + j) + 1. Since 3kj + k + j is an integer, xy is rough.

13. (a) 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35; 5·8 = 40 which is rough since 40 = 13(3)

+ 1. 8·11 = 88 which is rough since 88 = 3(29) + 1.

(b) If x and y are abrasive, then xy is rough.

(c) Since x is abrasive, there is an integer k such that x = 3k + 2. Since y is also abrasive, there is an integer j with y = 3j+ 2. Then xy = (3k + 2)(3j + 2) = 9kj +6k + 6j + 4 = 9kj + 6k + 6j + 3 + 1 = 3(3kj + 2k + 2j + 1) + 1. Since 3kj + 2k + 2j + 1 is an integer, xy is rough.

By way of contradiction, suppose that a2 is smooth and a is not smooth. Since a is not smooth, a must be either rough or abrasive.

Case 1: Suppose that a is rough. By Exercise 12, a · a = a2 is rough.

Case 2: Suppose that a is abrasive. By Exercise 13, a · a = a2 is rough.

Therefore it is not possible for a2 to be smooth and a not be smooth. We have a contradiction.

15. Suppose x = and x is rational. Then there are integers m and n (n  0) with

x = =

such that m and n have no common factors other than 1. Since = , we can square both sides of the equation to learn that

3 = or 3n2 = m2

Since m2 is the product of 3 and the integer n2, m2 is smooth. By Exercise 14 this means that m is smooth so there is an integer k with m = 3k. Thus m2 = (3k)2 = 9k2. Hence 3n2 = 9k2 and dividing by 3 reveals that n2 = 3k2. Using Exercise 14 once again indicates that since n2 is smooth, n is smooth. Now we have shown that both m and n are smooth, that is, 3 is a divisor or factor of both m and n. This contradicts our assumption that m and n share no common positive divisors other than 1.

16. (1) For all integers a, aa(mod 5) since 5 | (a – a). Thus the relation is reflexive.

(2)If ab(mod 5), then 5 | (a – b). Thus there is an integer k with(a – b) = 5k. Therefore

– (a –b) = – 5k or (b – a) = 5(–k). Thus 5 | (b – a) or ba (mod 5). Thus the relation is symmetric.

(3) If a b(mod 5) then 5 | (a – b). Thus there is an integer k with(a – b) = 5k. Similarly, if 5 | (b – c) there is an integer l with (b – c) = 5l; Thus (a – b) + (b – c) = 5k + 5l or (a – c) = 5k + 5l = 5(k + l). It follows that 5 | (a – c) and thata c(mod 5). Thus the relation is transitive.

17. Since n2 is even, by Theorem 12, n is even. Thus there is an integer k with n = 2k. It

follows that n2 = (2k)( 2k) = 4k2, and n2 is divisible by 4.

Teaching Notes, Section 3.3: Again, we encourage group work on Exploratory Exercises 1 through 3 before asking students to attempt proofs on their own.

After having done one or two induction proofs, students have a tendency to address those proofs mechanically without much thought about what is actually being accomplished. Careful attention to Exploratory Exercise 5 and Exercises 18 and 19 are a useful antidote to this tendency.

Exploratory Exercise Set 3.3

1. (a) 16; 25; 36

(b) n2

2. (a) 1 + 3 + 5 +…+ (2n 1) = n2

(b) P(1): 1 = 12 or 1 = 1 which is true.

P(2): 1 + 3 = 22 or 1 + 3 = 4 which is true.

P(3): 1 + 3 + 5 = 32 or 1 + 3 + 5 = 9 which is true.

P(k + 1): 1 + 3 + 5+…+ (2k 1) + (2(k + 1) – 1) = (k + 1)2 or

1 + 3 + 5 + … + (2k  1) + (2k + 1) = (k + 1)2

(d) Basis Step: P(1) is the statement that 1 = 12 or 1 = 1 which is true.

(e) (k + 1)2

(f) We have shown that P(n) is true for n = 1, and we have shown that for each positive integer k, when P(k) is true, P(k + 1) is true. By the Principle of Induction, P(n) is true for all positive integers n.

3. (a)4 divides.

(b) Find in text.

P(2): 4 | (62 – 22) or 4 | 32 which is true.

P(3): 4 | (63 – 23) or 4 | 208 which is true.

(d) P(k): 4 divides. P(k + 1): 4 divides.

= 6 · 6k – 2k+1 = (4 + 2) 6k – 2k+1 = 4 · 6k + 2 · 6k – 2 · 2k = 4 · 6k + 2 (6k – 2k).

(e) Basis Step: P(1) is the statement 4 | (6 – 2) or 4 | 4 which is true.

(f) In (d) we see that = 4 · 6k + 2(6k – 2k). By definition of “divides,” 4 divides 4·6k and by induction hypothesis, 4 | (6k – 2k). Theorem 9 then asserts that 4|2(6k – 2k) and Theorem 7 then allows us to conclude that 4 | .

4. (a) = 55

(b) S = 1 + 2 + 3 + … + 98 + 99 + 100

S = 100 + 99 + 98 + … + 3 + 2 + 1

2S = 101 + 101 + 101 + …. + 101+ 101 +101

Since the right side of the equation is the sum of 100 copies of 101,

2S = 100(101) or S = 5050.

S = n + (n –1) + (n –1) + … + 3 + 2 + 1

2S = (n +1) + (n +1) + (n +1) + …. + (n +1) + (n +1) + (n +1)

Since the right side of the equation is the sum of n copies of (n +1),

2S = n(n +1) or S = .

Answers will vary.

Exercise Set 3.3

1. Basis Step: 3 = .

Inductive Step: We wish to prove the statement “If P(k) and k  1, then P(k + 1).”

Our inductive hypothesis, then, is the statement P(k): 3 + 6 + 9 + …+ 3k = .

Add 3(k + 1) to both sides of the equation given in the inductive hypothesis and then perform algebraic manipulation on the right hand side of the resulting equation with these results.

3 + 6 + 9 + …+ 3k + 3(k + 1) = + 3(k + 1)

3 + 6 + 9 + …+ 3k + 3(k + 1) = +

3 + 6 + 9 + …+ 3k + 3(k + 1) = =

Since this last statement is P(k + 1), we have shown that when P(k) is true, P(k + 1) is true.

2.Basis Step: 12 = = = 1

Inductive Step: We wish to prove the statement “If P(k) and k  1, then P(k + 1)”

Our hypothesis, then, is the statement P(k): .

Add (k + 1)2 to both sides of the equation given in the inductive hypothesis and then perform algebraic manipulation on the right hand side of the resulting equation with these results.

Since this last statement is P(k + 1), we have shown that when P(k) is true, P(k + 1) is true.

3. Basis Step: 13 = .

Inductive Step: We wish to prove the statement “If P(k) and k  1, then P(k + 1)”

Our inductive hypothesis, then, is the statement P(k):

Add (k + 1)3 to both sides of the equation given in the inductive hypothesis and then perform algebraic manipulation on the right hand side of the resulting equation with these results.

Since this last statement is P(k + 1), we have shown that when P(k) is true, P(k + 1) is true.

4. Basis Step: 1 = = 1.

Inductive Step: We wish to prove the statement “If P(k) and k  1, then P(k + 1).”

P(k) is the statement, 1 + 4 + 7 + …+ (3k – 2) = . Add (3(k +1) – 2) = 3k+ 1 to both sides of this equation and manipulate the results algebraically.

1 + 4 + 7 + …+ (3k – 2) + (3k + 1) = + (3k + 1)

1 + 4 + 7 + …+ (3k – 2) + (3k + 1) =

Since this last statement is P(k + 1), we have shown that when P(k) is true, P(k + 1) is true.

5. Basis Step: 1 < 21 = 2.

Inductive Step: We wish to prove the statement “If P(k) and k  1, then P(k + 1).”

P(k) is the statement, k < 2k. Multiplying both sides of this statement by 2 yields

2k < 2·2k = 2k + 1

Since k  1, k + 1  k + k = 2k so k + 1  2k < 2k + 1. Since k + 1 < 2k + 1 is P(k + 1), we are done.

6. Basis Step: P(1) is the statement 5| (9 – 4) or 5 | 5 which is true.

.By definition of “divides,” 5 divides 5 · 9k and by induction hypothesis, 5 | (9k – 4k). Theorem 9 then asserts that 5|4(9k – 4k) and Theorem 7 then allows us to conclude that 5 | .

7. Basis Step: Since 31 1 = 2, 2 | (31 1).

Inductive Step: Assume that k is a natural number and 2 divides . Show this

ensures that 2 divides . We observe that