PS06: Proofs with Problems, and Induction

Due Wed 4/15 @ 1:30pm.

Here's a reiteration of the reminders from the last problem set:

Moving on, here's the problem set:

Do these problems from the book, listed on page 465.

  1. 4.89
  2. 4.90
  3. 4.92
  4. 4.93

Also do these problems, listed on pages 465 and 466. Make sure you read the note in the middle of p. 465; it pertains to these problems.

  1. 4.94
  2. 4.95
  3. 4.101
  4. 4.102
  5. 4.103

Also do these problems, listed on page 516. For each inductive proof you write, explicitly state your predicate, and make sure it's clear what your base case, inductive hypothesis, and inductive-case reasoning are. The proofs given in Examples 5.2 and 5.3 in the book (pages 505–507) are very good in this regard; yours should look similar. The book also gives a great “checklist” for good structure of inductive proofs on the bottom of page 507. I would add an additional point to the checklist: as step 4, explicitly invoke the principle of mathematical induction, and explicitly state the claim that you've proven. (Example 5.2 does this right at the end.)

  1. 5.1
  2. 5.7