Saturday, October 20, 2012

Strong Induction vs Complete Induction

So Professor Heap talked about Mathematical Induction and Complete Induction during the first weeks. Although I've done tons of Induction proofs, I've never heard of Complete Induction, so I looked it up on Google, and it seems to be just a different name of Strong Induction (http://en.wikipedia.org/wiki/Mathematical_induction#Complete_induction). Nonetheless, the structure of Complete Induction used by Professor Heap and the TAs is different from the Strong Induction I know. As far as I remember, you need Strong Induction only when one base case is not enough.

Example (taken from quiz#2): Prove that you can make n cents using only 2-cent and 3-cent coins using Strong Induction.

BCs:
n=2: use a 2-cent coin
n=3: use a 3-cent coin

IH: Assume P(2), P(3), ..., P(n) true

IS: Want P(n+1) true.
n+1 = (n-1) +2

Since n-1 >= 2, we can use IH: P(n-1) is true
By IH, we can make (n-1) cents using only 2-cent and 3-cent coin(s)

Thus, we can make (n-1) + 2 cents using another 2-cent coin.
Thus, P(n+1) is true as needed.

Conclusion: blah blah blah

The structure Professor Heap uses seems to put the Base Cases into one case in the IS (Induction Step), which confused me at first--it seems like a Proof by Cases in a Mathematical Induction. To me, I think the structure of Complete Induction / Strong Induction should be similar to that of Mathematical Induction as possible--it should be more intuitive that way.

No comments:

Post a Comment