Solution Set of Homework Assignment 4

Section 3.2

22. Let P(n) denote the proposition that 6 divides n3 - n whenever n is a nonnegative integer.

Basic Step: When n = 0, n3 - n = 0 so P(0) is true.

Inductive Step: We must show that the proposition P(n) P(n+1) is true for every

nonnegative integer n. Suppose that 6 divides n3 - n for every nonnegative integer. Assuming

P(n) is true, it follows that (n+1)3-(n+1) = n3+3n2+3n+1-n -1 = n3+3n2+2n = n3-n+3n2+3n =

(n3-n)+3n(n+1) and 3n(n+1) can be divided by 6. This shows that P(n+1) is true for every

nonnegative integer n. This completes the inductive step and completes the proof.

 

24. Let P(n) denote the proposition that n2-7n+12 0 whenever n is an integer greater than 3.

Basic Step: when n=4, n2-7n+12=0 so P(4) is true.

Inductive Step: Suppose that P(n) is true, that is, n2-7n+12 0 for every integer n s.t. n > 3.

Then it follows that (n+1)2-7(n+1)+12= n2-5n+6= (n2-7n+12)+(2n-6)>0. This shows that

P(n+1) is true for every integer n s.t. n > 3. This completes the inductive step and completes

the proof.

 

36. Let P(k) denote the proposition that if a and b are integers with a b (mod m) for a positive

integer, then ak bk (mod m) whenever k is a nonnegative integer.

Basic step: when k = 0, a0 b0 (mod m). Thus P(0) is true.

Inductive Step: Let k > 0. Suppose that P(k) is true, that is, if a and b are integers with a b

(mod m) for a positive integer, then ak bk (mod m). We can represent a and ak as a = mp + b

and ak = mq + bk respectively for integers p, q. It follows that ak+1 = ak a = (mq + bk ) (mp +

b) = mqmp + bkmp + mqb +bk+1 = m(mpq + bkp + qb) + bk+1 bk+1 (mod m). Thus P(k)

P(k+1) is true for every nonnegative integer. This completes the proof by induction.

 

43. See the textbook.