Discrete Mathematics for Computer Science

62 CHAPTER 1 Sets, Proof Templates, and Induction

Therefore, 0 E T.

(Inductive step) The remainder of the proof is left as an exercise for the reader. 0

Exercise 39 in Section 1.9 explores other properties of this algorithm.

rnExercises

Assume that all variables not given an explicit domain are elements of N.

1. Show that for n = 0, 1,^2 the following is true:

F^2 +2^2 +3^2 +..+n2 =n(n+l)(2n+1)/6

2. Find all the elements of {0, 1, 2, 31 that, when substituted for n, satisfy:
   1 1 1 - n
   1-- + +--.-• + ""+
   1.2 2.3 n(n+l) n+1


3. Write out the information that describes what the inductive step assumes and what the
   step must prove for proving

12 + 22 +^32 +... +n^2 = n(n + 1)(2n + 1)/6

with no given.

4. Write out the information that describes what the inductive step assumes and what the
   step must prove for proving

15±+2 5+3 5±+...±+fn5=!nl6 +In^5 +5 n4 _^1 n2

6 2 12 12

with no given.

5. Write out the information that describes what the inductive step assumes and what the
   step must prove for proving that 6 divides n^3 + 5n with no given.


6. Write out the information that describes what the inductive step assumes and what the
   step must prove for proving that 120 divides n^5 - 5n^3 + 4n with no given.

7. Show for n = O, 1, 2 that

(n + 1)(2n + 1)(2n + 3)/3 + (2n + 3)2 = (n + 2)(2n + 3)(2n + 5)/3

8. Show that

(n + 1)(2n + 1)(2n + 3)/3 + (2n + 3)2 = (n + 2)(2n + 3)(2n + 5)/3

9. Show that

n2 + n + 2(n + 1) = (n + 1)^2 + (n + 1)

10. Show that
    n

E F 2 i+i = F2n+2 - 1

i=0

forn = 1,2, 3,4.

11. For which elements n E {0, 1, 2, 3, 4, 51 does 6 divide n^3 + 5n?

12. Show that 8 divides k^2 - Ifor k e {1, 3, 5, 7}.