Spring 2015

CS 202: Math of CS

Jadrian Miles

Due Fri 4/17 @ 1:30pm.

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.)

Do these problems from the book, listed on pages 516–517.

- 5.5
- 5.9 — Don't worry about being ultra-formal and mathy with this proof. Instead, concentrate on following all the steps in the checklist.
- 5.23