__ __

**Solution Set of Homework Assignment 4**

**Section 3.2**

22. Let P(n) denote the proposition that 6 divides n^{3 }- n whenever n is a
nonnegative integer.

Basic Step: When n = 0, n^{3 }- 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 n^{3 }- n for every nonnegative
integer. Assuming

P(n) is true, it follows that (n+1)^{3}-(n+1) = n^{3}+3n^{2}+3n+1-n
-1 = n^{3}+3n^{2}+2n = n^{3}-n+3n^{2}+3n =

(n^{3}-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 n^{2}-7n+12 ³
0 whenever n is an integer greater than 3.

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

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

Then it follows that (n+1)^{2}-7(n+1)+12= n^{2}-5n+6= (n^{2}-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 a^{k} º b^{k} (mod m)
whenever k is a nonnegative integer.

Basic step: when k = 0, a^{0} º b^{0} (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 a^{k} º b^{k}
(mod m). We can represent a and a^{k} as a = mp + b

and a^{k} = mq + b^{k} respectively for integers p, q. It follows that
a^{k+1} = a^{k} × a^{ }= (mq + b^{k}
)× (mp +

b) = mqmp + b^{k}mp + mqb +b^{k+1} = m(mpq + b^{k}p + qb) + b^{k+1º }b^{k+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.