Recitation of Feb. 14, 2013

We discussed the coin removal problem (p.50 and 63 in your textbook) as an example of the method of strong induction.

The question was raised of whether strong induction is a legitimate method of proof: it is as legitimate as weak induction (so it is legitimate). There is a formal proof of the principle of strong induction from the principle of weak induction in your textbook.

Here is one way to see it: when proving that P(n) is true for all natural numbers n by weak induction, one proves P(1), then P(2), then P(3), etc... When proving e.g. P(5), we are assuming P(4), but why not assume also P(1), P(2), and P(3), since these have been proven "before" in the induction order.

We looked at Problem 3.57 in the text, dealing with recursively defined sequences of order 2. I explained why the base case must be proven for all the initial values. Problem 3.55 is an additional example I did not have time to cover.