I've always thought that if a predicate can be proven with mathematical induction, then it can be proven using complete induction just as easily and vice versa. It turns out I was wrong. Although there is a cycle for believing in well-ordering, mathematical induction, and complete induction as in WO => MI => CI => WO, the cycle is at the top level. At the working level where we have to do the actual proof using induction, sometimes the trasfer between MI <=> CI is not so smooth.
Such is the case for the quiz question in tutorial 3. For a given recurrence, we are supposed to prove using MI that for every positive natural number n, T(n) >= c lg(n), for some positive real constant c. I noticed that in all of the lecture slides about proving big-O or big-Omega, we use CI. The reason is clear to see, since working with floors or ceilings of n over some nautral number means we can use the induction hypothesis to eliminate the floor or ceiling; ceiling(n/k) is less than or equal to n for a large enough n. Then we can break up lg(n/k) to get lg(n). But how about MI? How do we prove that [T(n) >= c lg(n)] => [T(n + 1) >= c lg(n + 1)]? Logarithms do not work well with addition, because it cannot be broken up easily. When I saw the question, I was at a loss. Eventually I couldn't resist the temptation to use the induction hypothesis for CI on n + 1 for a MI proof, which is definitely not the right way to approach it. But hey, I had a limited amount of time on the quiz! It is interesting and useful to discover that choosing the right induction technique paves the way for presenting a clear proof.
No comments:
Post a Comment