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 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 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 be the statement   = .

Basis step: When ,   then   = .   Also   = .   Hence is true.

Inductive step: Assume that is true,   that is,   = .

Then

=

=

=

= .

Hence is true.