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