PS06: Proofs with Problems, and Induction

Due Wed 4/15 @ 1:30pm.

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

You should explicitly state the claim before you begin a proof. This is true not only in writing up a proof, but also when planning the proof. If you don't have a clear idea of the claim you're trying to prove, it's much harder to figure out how to prove it.
It often takes many attempts before you figure out how to prove something correctly.
Correctness is not our only criterion, either; clarity is also important. Sometimes, you figure out a way to prove something correctly, but the proof you invent is a big mess. It often takes more work, and perhaps an attempt with a completely different proof technique, to find a proof that is correct and clear.
The correct order of argument in a proof is sometimes the reverse of the order of the work you used to find the proof. This is discussed briefly on page 460, under the heading “Fallacy: Proving True”.
It often takes many drafts before you figure out how to write up a proof clearly.

Moving on, here's the problem set:

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

4.89
4.90
4.92
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.

4.94
4.95
4.101
4.102
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.)