Unit 16 Answers

1. Let P(n) be " 3 + 3 * 5 + 3 * 52+ ... + 3 * 5n = 3 (5n+1 - 1)/4 whenever n is a nonnegative integer".

Basis step: P(0) is true since 3*50 = 3 = 3 (50+1 - 1)/4

Inductive step: Assume that P(n) is true.  Then 3 + 3 * 5 + 3 * 52+ ... + 3 * 5n + 3 * 5n + 1
= 3 (5n+1 - 1 )/4 + 3 * 5n + 1
= ( 3 (5n+1 - 1) + 3*4*5n+1 )/4
= 3 ( 5n+2 - 1 )/4
= 3 ( 5(n+1)+1 - 1 )/4

Hence P(n + 1) is true.

2. Let P(n) be "1² + 3² + ... + (2n + 1)² = (n + 1)(2n + 1)(2n + 3)/3 whenever n is a nonnegative integer".

Basis step: P(0) is true since 1² = 1 = (0 + 1)(2*0 + 1)(2*0 + 3)/3. 

Inductive step: Assumethat P(n) is true. 
Then 1² + 3² + ... + (2n + 1)² + (2(n+ 1) + 1)²
= (n + 1)(2n + 1)(2n + 3)/3 + (2n + 3)²
= (2n + 3)[(n + 1)(2n + 1)/3 + (2n + 3)]
= (2n+ 3)(2n² + 9n + 10)/3
= (2n + 3)(2n + 5)(n +2)/3
= ((n+ 1) + 1)(2(n+1)+1)(2(n+1) + 3)/3.

Hence P(n + 1) is true.

3. Let P(n) be "2n > n² whenever n is an integer greater than 4 ".

Basis step: P(5) is true since 25 = 32 > 25 =5². 

Inductive step: Assume that P(n) is true, that is, 2n> n².  Then 2n+1 = 2*2n> n² + n² > n² + 4n geq.gif (893 bytes) n²+ 2n + 1 = (n+1)²  
since n > 4.

Hence P(n + 1) is true.

4. Let P(n) be "a postage of n cents can be formed using 3-cent and 5-cent stamps if n is greater than 7 ". 

Basis step: P(8) is true since 8 cents postage can be formed with one 3-cent and one 5-cent stamp. 

Inductive step: Assume that P(n) is true, that is, postage of n cents can be formed using 3-cent and 5-cent stamps.  We will show how to form postage of n + 1 cents.  By the inductive hypothesis postage of n cents can be formed using 3-cent and 5-cent stamps.  If this included a 5-cent stamp, replace this 5-cent stamp with two 3-cent stamps to obtain n + 1 cents postage.  Otherwise, only 3-cent stamps were used and n geq.gif (893 bytes) 9.  Hence there are at least three 3-cent stamps forming n cents. Remove three of these 3-cent stamps and replace them with two 5-cent stamps to obtain n + 1 cents postage.

Hence P(n + 1) is true.

5. Let P(n) be " n5 - n is divisible by 5 when n is a nonnegative integer ". 

Basis step: P(0) is true since 05- 0 = 0 and 0 is divisible by 5. 

Inductive step: Assume that P(n) is true, that is, n5 - 5 is divisible by 5. 
Then (n+1)5- (n+1)
= (n5 + 5n4+ 10n³ + 10n² + 5n + 1) - (n+1)
= (n5- n) + 5(n4 + 2n³ + 2n² + n), and the last quantity is also divisible by 5, since both terms in this sum are divisible by 5.

6. Let $P(n)$ be the statement   $\overline {\cup_{i = 1}^{n} A_{i}}$ = $\cap_{i=1}^{n} \overline{A_{i}}$.

Basis step: When $ i = 1$,   then   $\overline {\cup_{i = 1}^{1} A_{i}}$ = $\overline{A_{1}}$.   Also   $\cap_{i=1}^{1} \overline{A_{i}}$ = $\overline{A_{1}}$.   Hence $P(1)$ is true.

Inductive step: Assume that $P(n)$ is true,   that is,   $\overline {\cup_{i = 1}^{n} A_{i}}$ = $\cap_{i=1}^{n} \overline{A_{i}}$.

Then   $\overline {\cup_{i = 1}^{n+1} A_{i}}$

= $\overline {(\cup_{i = 1}^{n} A_{i}) \cup A_{n+1} }$

= $\overline {\cup_{i = 1}^{n} A_{i}} \cap \overline{A_{n+1}}$

= $\cap_{i=1}^{n} \overline{A_{i}} \cap \overline{A_{n+1}}$

= $\cap_{i=1}^{n+1} \overline{A_{i}}$.

Hence $P(n+1)$ is true.