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
1
2 + 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}.